oj.uz

Submission #1063235

# Submission time Handle Problem Language Result Execution time Memory
1063235 2024-08-17T15:38:35 Z _8_8_ Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 281 ms 780372 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 400 + 12, MOD = (int)1e9 + 7;

int n,dp[N][N][N][3];
vector<int> r,g,y;
void test() {
    cin >> n;
    string s;cin >> s;
    for(int i = 0;i < n;i++) {
        if(s[i] == 'R') {
            r.push_back(i);
        } else if(s[i] == 'Y') {
            y.push_back(i);
        } else {
            g.push_back(i);
        }
    }
    int r_ = (int)r.size(),g_ = (int)g.size(),y_ = (int)y.size();
    for(int i = 0;i <= n;i++) {
        for(int j = 0;j <= n;j++) {
            for(int k = 0;k <= n;k++) {
                for(int t = 0;t < 3;t++) {
                    dp[i][j][k][t] = 1e9;
                }
            }
        }
    }
    for(int i = 0;i < 3;i++) {
        dp[0][0][0][i] = 0;
    }
    for(int i = 0;i <= r_;i++) {
        for(int j = 0;j <= g_;j++) {
            for(int k = 0;k <= y_;k++) {
                for(int t = 0;t < 3;t++){
                    int all = i + j + k;
                    if(i < r_ && t != 0) {
                        dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0],dp[i][j][k][t] + abs(all - r[i]));
                    }
                    if(j < g_ && t != 1) {
                        dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1],dp[i][j][k][t] + abs(all - g[j]));
                    }
                    if(k < y_ && t != 2) {
                        dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2],dp[i][j][k][t] + abs(all - y[k]));
                    }
                }
            }
        }
    }
    int res = 1e9;
    for(int i = 0;i < 3;i++) {
        res = min(res,dp[r_][g_][y_][i]);
    }
    if(res == 1e9) {
        cout << -1;
        return;
    }
    cout << res / 2;
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 12892 KB Output is correct
5 Correct 1 ms 15452 KB Output is correct
6 Correct 1 ms 13404 KB Output is correct
7 Correct 1 ms 13404 KB Output is correct
8 Correct 1 ms 11356 KB Output is correct
9 Correct 2 ms 13404 KB Output is correct
10 Correct 2 ms 13404 KB Output is correct
11 Incorrect 2 ms 13404 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 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 12892 KB Output is correct
5 Correct 1 ms 15452 KB Output is correct
6 Correct 1 ms 13404 KB Output is correct
7 Correct 1 ms 13404 KB Output is correct
8 Correct 1 ms 11356 KB Output is correct
9 Correct 2 ms 13404 KB Output is correct
10 Correct 2 ms 13404 KB Output is correct
11 Incorrect 2 ms 13404 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 6492 KB Output is correct
2 Correct 242 ms 780188 KB Output is correct
3 Correct 258 ms 776196 KB Output is correct
4 Correct 259 ms 779976 KB Output is correct
5 Correct 269 ms 780044 KB Output is correct
6 Correct 281 ms 780116 KB Output is correct
7 Correct 259 ms 776244 KB Output is correct
8 Correct 253 ms 776504 KB Output is correct
9 Correct 264 ms 772432 KB Output is correct
10 Correct 252 ms 780372 KB Output is correct
11 Correct 270 ms 780372 KB Output is correct
12 Correct 67 ms 216148 KB Output is correct
13 Correct 123 ms 373076 KB Output is correct
14 Correct 181 ms 534612 KB Output is correct
15 Correct 246 ms 780116 KB Output is correct
16 Correct 259 ms 780116 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 12892 KB Output is correct
5 Correct 1 ms 15452 KB Output is correct
6 Correct 1 ms 13404 KB Output is correct
7 Correct 1 ms 13404 KB Output is correct
8 Correct 1 ms 11356 KB Output is correct
9 Correct 2 ms 13404 KB Output is correct
10 Correct 2 ms 13404 KB Output is correct
11 Incorrect 2 ms 13404 KB Output isn't correct
12 Halted 0 ms 0 KB -