oj.uz

Submission #375990

# Submission time Handle Problem Language Result Execution time Memory
375990 2021-03-10T14:31:13 Z valerikk Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 446 ms 792196 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 407;
const int INF = 0x3f3f3f3f;

int dp[N][N][N][3];

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    vector<int> r, g, y;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'R')
            r.push_back(i);
        if (s[i] == 'G')
            g.push_back(i);
        if (s[i] == 'Y')
            y.push_back(i);
    }
    int red = r.size(), green = g.size(), yellow = y.size();
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < 3; ++i)
        dp[0][0][0][i] = 0;
    for (int i = 0; i <= red; ++i) {
        for (int j = 0; j <= green; ++j) {
            for (int k = 0; k <= yellow; ++k) {
                for (int last = 0; last < 3; ++last) {
                    int pos = i + j + k;
                    int val = dp[i][j][k][last];
                    if (val == INF)
                        continue;
                    if (i < red && last != 0) dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], val + abs(pos - r[i]));
                    if (j < green && last != 1) dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], val + abs(pos - g[j]));
                    if (k < yellow && last != 2) dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], val + abs(pos - y[k]));
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < 3; ++i)
        ans = min(ans, dp[red][green][yellow][i]);
    if (ans == INF) {
        cout << -1 << endl;
        return 0;
    }
    cout << ans / 2 << endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 791916 KB Output is correct
2 Correct 446 ms 791928 KB Output is correct
3 Correct 412 ms 791916 KB Output is correct
4 Correct 412 ms 791900 KB Output is correct
5 Correct 437 ms 792044 KB Output is correct
6 Correct 407 ms 791916 KB Output is correct
7 Correct 409 ms 791916 KB Output is correct
8 Correct 407 ms 791916 KB Output is correct
9 Correct 411 ms 791996 KB Output is correct
10 Correct 409 ms 791916 KB Output is correct
11 Incorrect 405 ms 792044 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 791916 KB Output is correct
2 Correct 446 ms 791928 KB Output is correct
3 Correct 412 ms 791916 KB Output is correct
4 Correct 412 ms 791900 KB Output is correct
5 Correct 437 ms 792044 KB Output is correct
6 Correct 407 ms 791916 KB Output is correct
7 Correct 409 ms 791916 KB Output is correct
8 Correct 407 ms 791916 KB Output is correct
9 Correct 411 ms 791996 KB Output is correct
10 Correct 409 ms 791916 KB Output is correct
11 Incorrect 405 ms 792044 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 438 ms 791992 KB Output is correct
2 Correct 416 ms 792172 KB Output is correct
3 Correct 425 ms 791936 KB Output is correct
4 Correct 412 ms 792044 KB Output is correct
5 Correct 411 ms 791916 KB Output is correct
6 Correct 410 ms 791916 KB Output is correct
7 Correct 424 ms 791920 KB Output is correct
8 Correct 406 ms 792044 KB Output is correct
9 Correct 425 ms 792044 KB Output is correct
10 Correct 409 ms 791916 KB Output is correct
11 Correct 428 ms 792156 KB Output is correct
12 Correct 409 ms 792196 KB Output is correct
13 Correct 422 ms 791916 KB Output is correct
14 Correct 428 ms 791916 KB Output is correct
15 Correct 408 ms 791916 KB Output is correct
16 Correct 413 ms 791916 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 791916 KB Output is correct
2 Correct 446 ms 791928 KB Output is correct
3 Correct 412 ms 791916 KB Output is correct
4 Correct 412 ms 791900 KB Output is correct
5 Correct 437 ms 792044 KB Output is correct
6 Correct 407 ms 791916 KB Output is correct
7 Correct 409 ms 791916 KB Output is correct
8 Correct 407 ms 791916 KB Output is correct
9 Correct 411 ms 791996 KB Output is correct
10 Correct 409 ms 791916 KB Output is correct
11 Incorrect 405 ms 792044 KB Output isn't correct
12 Halted 0 ms 0 KB -