oj.uz

Submission #1089414

# Submission time Handle Problem Language Result Execution time Memory
1089414 2024-09-16T12:43:16 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 128 ms 326448 KB 
#include <bits/stdc++.h>

#define int         long long
#define all(x)     x.begin(), x.end()
#define allr(x)     x.rbegin(), x.rend()
#define sz          size()
#define yes      "YES"
#define no      "NO"
#define IOI      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pf      push_front
#define pb      push_back
#define S      second
#define F      first

using namespace std;

const int N = 400 + 5;
const int NN = 1e5;
const int mod = (1e9 + 7);
const int inf = 1e18;

int n, pref[3][N], dp[N][N][N][4];
vector<int> g[3];
string s;

void legenda_ne_umret() {
    cin >> n >> s;
    s = '+' + s;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'Y') {
            g[0].pb(i);
        }
        if (s[i] == 'R') {
            g[1].pb(i);
        }
        if (s[i] == 'G') {
            g[2].pb(i);
        }
        pref[0][i] = pref[0][i - 1] + (s[i] == 'Y');
        pref[1][i] = pref[1][i - 1] + (s[i] == 'R');
        pref[2][i] = pref[2][i - 1] + (s[i] == 'G');

    }

    int allr = pref[1][n];
    int ally = pref[0][n];
    int allg = pref[2][n];

    for (int id = 0; id <= n; id++) {
        for (int a = 0; a <= allr; a++) {
            for (int b = 0; b <= ally; b++) {
                dp[id][a][b][0] = inf;
                dp[id][a][b][1] = inf;
                dp[id][a][b][2] = inf;
            }
        }
    }

    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;

    for (int id = 1; id <= n; id++) {
        for (int a = 0; a <= allr ; a++) {
            for (int b = 0; b <= ally; b++) {
                int c = id - a - b;
                if(c>allg || a + b > id)continue;
                if (a > 0) {
                    int pos = g[1][a - 1];
                    int cnt = max(0ll , b - pref[0][pos]) + max(0ll , c - pref[2][pos]);
                    dp[id][a][b][0] = min(dp[id - 1][a - 1][b][1], dp[id - 1][a - 1][b][2]) + max(0ll, (pos + cnt) - id);
                }
                if (b > 0) {
                    int pos = g[0][b - 1];
                    int cnt = max(0ll , a - pref[1][pos]) + max(0ll , c - pref[2][pos]);
                    dp[id][a][b][1] = min(dp[id - 1][a][b - 1][0], dp[id - 1][a][b - 1][2]) + max(0ll, (pos + cnt) - id);
                }
                if (c > 0) {
                    int pos = g[2][c - 1];
                    int cnt = max(0ll , b - pref[0][pos]) + max(0ll , a - pref[1][pos]);
                    dp[id][a][b][2] = min(dp[id - 1][a][b][0], dp[id - 1][a][b][1]) + max(0ll, (pos + cnt) - id);
                }
            }
        }
    }

    cout << (min({dp[n][allr][ally][0], dp[n][allr][ally][1], dp[n][allr][ally][2]}) == inf ? -1 : min({dp[n][allr][ally][0], dp[n][allr][ally][1], dp[n][allr][ally][2]}));
}



signed main() {
//    IOI;
//    freopen("maze.in", "r", stdin);
//    freopen("maze.out", "w", stdout);
/////////////////////////////////////////////
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case " << i << ":\n";
        legenda_ne_umret();
        cout << '\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 0 ms 964 KB Output is correct
10 Correct 0 ms 1116 KB Output is correct
11 Correct 0 ms 704 KB Output is correct
12 Correct 0 ms 860 KB Output is correct
13 Incorrect 0 ms 604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 0 ms 964 KB Output is correct
10 Correct 0 ms 1116 KB Output is correct
11 Correct 0 ms 704 KB Output is correct
12 Correct 0 ms 860 KB Output is correct
13 Incorrect 0 ms 604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 128 ms 326320 KB Output is correct
3 Correct 98 ms 325588 KB Output is correct
4 Correct 98 ms 326228 KB Output is correct
5 Correct 98 ms 326448 KB Output is correct
6 Correct 104 ms 326228 KB Output is correct
7 Correct 107 ms 324020 KB Output is correct
8 Correct 108 ms 323920 KB Output is correct
9 Correct 109 ms 323208 KB Output is correct
10 Correct 110 ms 326408 KB Output is correct
11 Correct 117 ms 326224 KB Output is correct
12 Correct 34 ms 87900 KB Output is correct
13 Correct 54 ms 154076 KB Output is correct
14 Correct 96 ms 222904 KB Output is correct
15 Correct 107 ms 324956 KB Output is correct
16 Correct 107 ms 324688 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 0 ms 964 KB Output is correct
10 Correct 0 ms 1116 KB Output is correct
11 Correct 0 ms 704 KB Output is correct
12 Correct 0 ms 860 KB Output is correct
13 Incorrect 0 ms 604 KB Output isn't correct
14 Halted 0 ms 0 KB -