oj.uz

Submission #481426

# Submission time Handle Problem Language Result Execution time Memory
481426 2021-10-20T19:04:56 Z Lobo Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
60 / 100
 491 ms 1048580 KB 
#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 450

ii n, dp[maxn][maxn][maxn][4];
ii qtd1, qtd2, qtd3;
ii pos1[maxn], pos2[maxn], pos3[maxn];
ii cnt1[maxn], cnt2[maxn], cnt3[maxn];
string s;

ii sol(ii c1, ii c2, ii c3, ii ant) {
    if(dp[c1][c2][c3][ant] != -1) return dp[c1][c2][c3][ant];

    ii ans = INFii;

    if(c1 != qtd1 && ant != 1) {
        ans = min(ans, sol(c1+1,c2,c3,1) + max(0,cnt2[pos2[c2]]-cnt2[pos1[c1+1]]) + max(0,cnt3[pos3[c3]]-cnt3[pos1[c1+1]]));
    }

    if(c2 != qtd2 && ant != 2) {
        ans = min(ans, sol(c1,c2+1,c3,2) + max(0,cnt1[pos1[c1]]-cnt1[pos2[c2+1]]) + max(0,cnt3[pos3[c3]]-cnt3[pos2[c2+1]]));
    }

    if(c3 != qtd3 && ant != 3) {
        ans = min(ans, sol(c1,c2,c3+1,3) + max(0,cnt2[pos2[c2]]-cnt2[pos3[c3+1]]) + max(0,cnt1[pos1[c1]]-cnt1[pos3[c3+1]]));
    }

    return dp[c1][c2][c3][ant] = ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    cin >> n >> s;

    for(ii i = 1; i <= n; i++) {
        cnt1[i] = cnt1[i-1];
        cnt2[i] = cnt2[i-1];
        cnt3[i] = cnt3[i-1];

        if(s[i-1] == 'R') {
            cnt1[i]++;
            pos1[++qtd1] = i;
        }
        if(s[i-1] == 'G') {
            cnt2[i]++;
            pos2[++qtd2] = i;
        }
        if(s[i-1] == 'Y') {
            cnt3[i]++;
            pos3[++qtd3] = i;
        }
    }

    for(ii i = 0; i <= n; i++) {
        for(ii j = 0; j <= n; j++) {
            for(ii k = 0; k <= n; k++) {
                dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = dp[i][j][k][3] = -1;
            }
        }
    }

    if(qtd1 > (n+1)/2 || qtd2 > (n+1)/2 || qtd3 > (n+1)/2) {
        cout << -1 << endl;
        return 0;
    }
    
    dp[qtd1][qtd2][qtd3][0] = dp[qtd1][qtd2][qtd3][1] = dp[qtd1][qtd2][qtd3][2] = dp[qtd1][qtd2][qtd3][3]  = 0;
    cout << sol(0,0,0,0) << endl;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 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 896 KB Output is correct
5 Correct 1 ms 1348 KB Output is correct
6 Correct 1 ms 1356 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 2 ms 1356 KB Output is correct
12 Correct 1 ms 1396 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 1216 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 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 896 KB Output is correct
5 Correct 1 ms 1348 KB Output is correct
6 Correct 1 ms 1356 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 2 ms 1356 KB Output is correct
12 Correct 1 ms 1396 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 1216 KB Output is correct
18 Correct 9 ms 18992 KB Output is correct
19 Correct 9 ms 18892 KB Output is correct
20 Correct 8 ms 18892 KB Output is correct
21 Correct 7 ms 18892 KB Output is correct
22 Correct 7 ms 18924 KB Output is correct
23 Correct 9 ms 18892 KB Output is correct
24 Correct 7 ms 18892 KB Output is correct
25 Correct 7 ms 18892 KB Output is correct
26 Correct 7 ms 18916 KB Output is correct
27 Correct 7 ms 18888 KB Output is correct
28 Correct 7 ms 18892 KB Output is correct
29 Correct 8 ms 18924 KB Output is correct
30 Correct 8 ms 18884 KB Output is correct
31 Correct 8 ms 18884 KB Output is correct
32 Correct 10 ms 18884 KB Output is correct
33 Correct 7 ms 18252 KB Output is correct
34 Correct 8 ms 18252 KB Output is correct
35 Correct 8 ms 17632 KB Output is correct
36 Correct 7 ms 18272 KB Output is correct
37 Correct 6 ms 16968 KB Output is correct
38 Correct 7 ms 18892 KB Output is correct
39 Correct 7 ms 18892 KB Output is correct
40 Correct 7 ms 18252 KB Output is correct
41 Correct 7 ms 18892 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Runtime error 491 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 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 896 KB Output is correct
5 Correct 1 ms 1348 KB Output is correct
6 Correct 1 ms 1356 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 2 ms 1356 KB Output is correct
12 Correct 1 ms 1396 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 1216 KB Output is correct
18 Correct 9 ms 18992 KB Output is correct
19 Correct 9 ms 18892 KB Output is correct
20 Correct 8 ms 18892 KB Output is correct
21 Correct 7 ms 18892 KB Output is correct
22 Correct 7 ms 18924 KB Output is correct
23 Correct 9 ms 18892 KB Output is correct
24 Correct 7 ms 18892 KB Output is correct
25 Correct 7 ms 18892 KB Output is correct
26 Correct 7 ms 18916 KB Output is correct
27 Correct 7 ms 18888 KB Output is correct
28 Correct 7 ms 18892 KB Output is correct
29 Correct 8 ms 18924 KB Output is correct
30 Correct 8 ms 18884 KB Output is correct
31 Correct 8 ms 18884 KB Output is correct
32 Correct 10 ms 18884 KB Output is correct
33 Correct 7 ms 18252 KB Output is correct
34 Correct 8 ms 18252 KB Output is correct
35 Correct 8 ms 17632 KB Output is correct
36 Correct 7 ms 18272 KB Output is correct
37 Correct 6 ms 16968 KB Output is correct
38 Correct 7 ms 18892 KB Output is correct
39 Correct 7 ms 18892 KB Output is correct
40 Correct 7 ms 18252 KB Output is correct
41 Correct 7 ms 18892 KB Output is correct
42 Correct 1 ms 332 KB Output is correct
43 Runtime error 491 ms 1048580 KB Execution killed with signal 9
44 Halted 0 ms 0 KB -