oj.uz

Submission #557000

# Submission time Handle Problem Language Result Execution time Memory
557000 2022-05-04T14:26:04 Z alextodoran Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 66 ms 162944 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 400;

int N;
string S;

int A[N_MAX + 2], cnta;
int B[N_MAX + 2], cntb;
int C[N_MAX + 2], cntc;

int dp[N_MAX + 2][N_MAX + 2][N_MAX + 2][3];

void update (int &x, const int &y) {
    if (y < x) {
        x = y;
    }
}

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

    cin >> N;
    cin >> S;
    for (int i = 0; i < N; i++) {
        if (S[i] == 'R') {
            cnta++;
            A[cnta] = i - (cnta - 1);
        } else if (S[i] == 'G') {
            cntb++;
            B[cntb] = i - (cntb - 1);
        } else {
            cntc++;
            C[cntc] = i - (cntc - 1);
        }
    }

    for (int a = 0; a <= cnta; a++) {
        for (int b = 0; b <= cntb; b++) {
            for (int c = 0; c <= cntc; c++) {
                dp[a][b][c][0] = INT_MAX / 2;
                dp[a][b][c][1] = INT_MAX / 2;
                dp[a][b][c][2] = INT_MAX / 2;
            }
        }
    }
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    for (int a = 0; a <= cnta; a++) {
        for (int b = 0; b <= cntb; b++) {
            for (int c = 0; c <= cntc; c++) {
                if (a < cnta) {
                    update(dp[a + 1][b][c][0], min(dp[a][b][c][2], dp[a][b][c][1]) + abs(b + c - A[a + 1]));
                }
                if (b < cntb) {
                    update(dp[a][b + 1][c][1], min(dp[a][b][c][0], dp[a][b][c][2]) + abs(c + a - B[b + 1]));
                }
                if (c < cntc) {
                    update(dp[a][b][c + 1][2], min(dp[a][b][c][1], dp[a][b][c][0]) + abs(a + b - C[c + 1]));
                }
            }
        }
    }
    int answer = INT_MAX / 2;
    answer = min(answer, dp[cnta][cntb][cntc][0]);
    answer = min(answer, dp[cnta][cntb][cntc][1]);
    answer = min(answer, dp[cnta][cntb][cntc][2]);
    cout << (answer != INT_MAX / 2 ? answer / 2 : -1) << "\n";

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 580 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Incorrect 1 ms 468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 580 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Incorrect 1 ms 468 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 0 ms 340 KB Output is correct
2 Correct 59 ms 162872 KB Output is correct
3 Correct 62 ms 162048 KB Output is correct
4 Correct 64 ms 162880 KB Output is correct
5 Correct 60 ms 162876 KB Output is correct
6 Correct 62 ms 162936 KB Output is correct
7 Correct 66 ms 162148 KB Output is correct
8 Correct 58 ms 162100 KB Output is correct
9 Correct 60 ms 161356 KB Output is correct
10 Correct 60 ms 162944 KB Output is correct
11 Correct 60 ms 162888 KB Output is correct
12 Correct 17 ms 43988 KB Output is correct
13 Correct 29 ms 77092 KB Output is correct
14 Correct 39 ms 111308 KB Output is correct
15 Correct 58 ms 162920 KB Output is correct
16 Correct 59 ms 162916 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 580 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Incorrect 1 ms 468 KB Output isn't correct
12 Halted 0 ms 0 KB -