oj.uz

Submission #512601

# Submission time Handle Problem Language Result Execution time Memory
512601 2022-01-16T13:33:50 Z Jarif_Rahman Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
75 / 100
 500 ms 755744 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int inf = 1e9+5;
int dp[400][401][401][3];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; str ss; cin >> n >> ss;
    vector<int> s;
    for(int i = 0; i < n; i++){
        if(ss[i] == 'R') s.pb(0);
        if(ss[i] == 'G') s.pb(1);
        if(ss[i] == 'Y') s.pb(2);
    }

    vector<vector<int>> cnt(n, vector<int>(3, 0));
    vector<vector<int>> pos(3);
    for(int i = 0; i < n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++)
        for(int c = 0; c < 3; c++) dp[i][j][k][c] = inf;

    for(int i = n-1; i >= 0; i--){
        pos[s[i]].pb(i);
        if(i != n-1) cnt[i][0] = cnt[i+1][0], cnt[i][1] = cnt[i+1][1], cnt[i][2] = cnt[i+1][2];
        cnt[i][s[i]]++;
    }

    for(int i = n-1; i >= 0; i--){
        int c[3];
        for(c[0] = 0; c[0] <= min(cnt[0][0], n-i); c[0]++) for(c[1] = 0; c[1] <= cnt[0][1] && c[1]+c[0] <= n-i; c[1]++){
            c[2] = n-i-c[0]-c[1];
            if(c[2] > cnt[0][2]) continue;
            for(int cl = 0; cl < 3; cl++){
                if(c[cl] == 0) continue;
                if(c[cl] > pos[cl].size()) continue;
                vector<int> o;
                for(int j = 0; j < 3; j++) if(j != cl) o.pb(j);
                for(int j = 0; j < 2; j++){
                    int cur = 0;
                    c[cl]--;
                    if(i != n-1) cur+=dp[i+1][c[0]][c[1]][o[j]];
                    c[cl]++;
                    if(i == n-1) cur+=abs(pos[cl][c[cl]-1]-i);
                    else cur+=abs(pos[cl][c[cl]-1]-max(0, c[o[0]]-cnt[pos[cl][c[cl]-1]][o[0]])
                        -max(0, c[o[1]]-cnt[pos[cl][c[cl]-1]][o[1]])-i);

                    dp[i][c[0]][c[1]][cl] = min(dp[i][c[0]][c[1]][cl], cur);
                }
            }
        }
    }
    int ans = inf;
    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int c = 0; c < 3; c++)
        ans = min(ans, dp[0][i][j][c]);
    if(ans >= inf) ans = -1;
    cout << ans << "\n";
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |                 if(c[cl] > pos[cl].size()) continue;
      |                    ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 1356 KB Output is correct
9 Correct 1 ms 1356 KB Output is correct
10 Correct 1 ms 1356 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 1 ms 1356 KB Output is correct
13 Correct 1 ms 1356 KB Output is correct
14 Correct 1 ms 1228 KB Output is correct
15 Correct 1 ms 1356 KB Output is correct
16 Correct 1 ms 1356 KB Output is correct
17 Correct 1 ms 1228 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 1356 KB Output is correct
9 Correct 1 ms 1356 KB Output is correct
10 Correct 1 ms 1356 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 1 ms 1356 KB Output is correct
13 Correct 1 ms 1356 KB Output is correct
14 Correct 1 ms 1228 KB Output is correct
15 Correct 1 ms 1356 KB Output is correct
16 Correct 1 ms 1356 KB Output is correct
17 Correct 1 ms 1228 KB Output is correct
18 Correct 9 ms 17612 KB Output is correct
19 Correct 9 ms 17736 KB Output is correct
20 Correct 9 ms 17612 KB Output is correct
21 Correct 9 ms 17740 KB Output is correct
22 Correct 8 ms 17740 KB Output is correct
23 Correct 9 ms 17612 KB Output is correct
24 Correct 9 ms 17612 KB Output is correct
25 Correct 7 ms 17612 KB Output is correct
26 Correct 7 ms 17612 KB Output is correct
27 Correct 8 ms 17684 KB Output is correct
28 Correct 9 ms 17612 KB Output is correct
29 Correct 10 ms 17704 KB Output is correct
30 Correct 9 ms 17640 KB Output is correct
31 Correct 9 ms 17732 KB Output is correct
32 Correct 9 ms 17736 KB Output is correct
33 Correct 8 ms 17100 KB Output is correct
34 Correct 8 ms 17100 KB Output is correct
35 Correct 10 ms 16460 KB Output is correct
36 Correct 9 ms 17108 KB Output is correct
37 Correct 8 ms 15960 KB Output is correct
38 Correct 9 ms 17752 KB Output is correct
39 Correct 9 ms 17752 KB Output is correct
40 Correct 7 ms 17100 KB Output is correct
41 Correct 8 ms 17612 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 341 ms 755528 KB Output is correct
3 Correct 332 ms 753340 KB Output is correct
4 Correct 378 ms 755452 KB Output is correct
5 Correct 332 ms 755524 KB Output is correct
6 Correct 339 ms 755520 KB Output is correct
7 Correct 337 ms 753376 KB Output is correct
8 Correct 335 ms 753356 KB Output is correct
9 Correct 332 ms 749572 KB Output is correct
10 Correct 344 ms 755564 KB Output is correct
11 Correct 333 ms 755428 KB Output is correct
12 Correct 81 ms 201800 KB Output is correct
13 Correct 149 ms 356052 KB Output is correct
14 Correct 219 ms 515856 KB Output is correct
15 Correct 332 ms 755456 KB Output is correct
16 Correct 336 ms 755744 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 1356 KB Output is correct
9 Correct 1 ms 1356 KB Output is correct
10 Correct 1 ms 1356 KB Output is correct
11 Correct 1 ms 1356 KB Output is correct
12 Correct 1 ms 1356 KB Output is correct
13 Correct 1 ms 1356 KB Output is correct
14 Correct 1 ms 1228 KB Output is correct
15 Correct 1 ms 1356 KB Output is correct
16 Correct 1 ms 1356 KB Output is correct
17 Correct 1 ms 1228 KB Output is correct
18 Correct 9 ms 17612 KB Output is correct
19 Correct 9 ms 17736 KB Output is correct
20 Correct 9 ms 17612 KB Output is correct
21 Correct 9 ms 17740 KB Output is correct
22 Correct 8 ms 17740 KB Output is correct
23 Correct 9 ms 17612 KB Output is correct
24 Correct 9 ms 17612 KB Output is correct
25 Correct 7 ms 17612 KB Output is correct
26 Correct 7 ms 17612 KB Output is correct
27 Correct 8 ms 17684 KB Output is correct
28 Correct 9 ms 17612 KB Output is correct
29 Correct 10 ms 17704 KB Output is correct
30 Correct 9 ms 17640 KB Output is correct
31 Correct 9 ms 17732 KB Output is correct
32 Correct 9 ms 17736 KB Output is correct
33 Correct 8 ms 17100 KB Output is correct
34 Correct 8 ms 17100 KB Output is correct
35 Correct 10 ms 16460 KB Output is correct
36 Correct 9 ms 17108 KB Output is correct
37 Correct 8 ms 15960 KB Output is correct
38 Correct 9 ms 17752 KB Output is correct
39 Correct 9 ms 17752 KB Output is correct
40 Correct 7 ms 17100 KB Output is correct
41 Correct 8 ms 17612 KB Output is correct
42 Correct 0 ms 332 KB Output is correct
43 Correct 341 ms 755528 KB Output is correct
44 Correct 332 ms 753340 KB Output is correct
45 Correct 378 ms 755452 KB Output is correct
46 Correct 332 ms 755524 KB Output is correct
47 Correct 339 ms 755520 KB Output is correct
48 Correct 337 ms 753376 KB Output is correct
49 Correct 335 ms 753356 KB Output is correct
50 Correct 332 ms 749572 KB Output is correct
51 Correct 344 ms 755564 KB Output is correct
52 Correct 333 ms 755428 KB Output is correct
53 Correct 81 ms 201800 KB Output is correct
54 Correct 149 ms 356052 KB Output is correct
55 Correct 219 ms 515856 KB Output is correct
56 Correct 332 ms 755456 KB Output is correct
57 Correct 336 ms 755744 KB Output is correct
58 Execution timed out 841 ms 755548 KB Time limit exceeded
59 Halted 0 ms 0 KB -