oj.uz

Submission #878990

# Submission time Handle Problem Language Result Execution time Memory
878990 2023-11-26T03:40:36 Z niter Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 54 ms 305552 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ins isnert
#define pii pair<int,int>
#define ff first
#define ss second
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) (x).begin(), (x).end()
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());

int a[405], cnt[3];
vector<int> pos[3];
int dp[405][405][405][3];
bool vis[405][405][405][3];
const int INF = 1e8;

inline void upd(int &x, int y){
    x = min(x, y);
}
inline int pos_diff(int ca, int cb, int cc, int last){
    int now = ca + cb + cc - 1; // 0-based
    if(last == 0){
        return abs(now - pos[0][ca]);
    }
    if(last == 1){
        return abs(now - pos[1][cb]);
    }
    if(last == 2){
        return abs(now - pos[2][cc]);
    }
    exit(1);
}
int cac(int ca, int cb, int cc, int last){
    if(ca < 0 || cb < 0 || cc < 0) return INF;
    if(ca == 0 && cb == 0 && cc == 0) return 0;
    if(last == 0 && ca == 0) return INF;
    if(last == 1 && cb == 0) return INF;
    if(last == 2 && cc == 0) return INF;
    if(vis[ca][cb][cc][last]) return dp[ca][cb][cc][last];
    loop(i,0,3){
        if(i == last) continue;
        int ret = cac(ca-(last == 0), cb-(last == 1), cc-(last == 2), i) + pos_diff(ca, cb, cc, last);
        upd(dp[ca][cb][cc][last], ret);
    }
    return dp[ca][cb][cc][last];
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
//    freopen("in.txt", "r", stdin);
    int n; string s;
    cin >> n >> s;
    loop(i,0,3) pos[i].pb(-999);
    loop(i,0,n){
        if(s[i] == 'R') a[i] = 0;
        else if(s[i] == 'G') a[i] = 1;
        else a[i] = 2;
        cnt[a[i]]++;
        pos[a[i]].pb(i);
    }
    loop(i,0,cnt[0]+1)
        loop(j,0,cnt[1]+1)
            loop(k,0,cnt[2]+1)
                loop(l,0,3)
                    dp[i][j][k][l] = INF;
    loop(i,0,3){
        vis[0][0][0][i] = true;
        dp[0][0][0][i] = 0;
    }
    loop(i,0,3){
        if(cnt[i] != 0)
            cac(cnt[0], cnt[1], cnt[2], i);
    }
    int ans = INF;
    loop(i,0,3) ans = min(ans, dp[cnt[0]][cnt[1]][cnt[2]][i]);
    if(ans == INF) cout << "-1\n";
    else cout << (ans >> 1) << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 12768 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 3 ms 14708 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 3 ms 22876 KB Output is correct
11 Incorrect 2 ms 12636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 12768 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 3 ms 14708 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 3 ms 22876 KB Output is correct
11 Incorrect 2 ms 12636 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 46 ms 305500 KB Output is correct
3 Correct 51 ms 305048 KB Output is correct
4 Correct 47 ms 305552 KB Output is correct
5 Correct 47 ms 305492 KB Output is correct
6 Correct 54 ms 305504 KB Output is correct
7 Correct 50 ms 304776 KB Output is correct
8 Correct 47 ms 304732 KB Output is correct
9 Correct 47 ms 304304 KB Output is correct
10 Correct 48 ms 305488 KB Output is correct
11 Correct 47 ms 305496 KB Output is correct
12 Correct 21 ms 201552 KB Output is correct
13 Correct 27 ms 251484 KB Output is correct
14 Correct 34 ms 271448 KB Output is correct
15 Correct 45 ms 304812 KB Output is correct
16 Correct 48 ms 304940 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 12768 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 2 ms 16732 KB Output is correct
8 Correct 3 ms 14708 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 3 ms 22876 KB Output is correct
11 Incorrect 2 ms 12636 KB Output isn't correct
12 Halted 0 ms 0 KB -