oj.uz

Submission #556997

# Submission time Handle Problem Language Result Execution time Memory
556997 2022-05-04T14:18:56 Z alextodoran Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 68 ms 162912 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]; int cnta;
int B[N_MAX + 2]; int cntb;
int C[N_MAX + 2]; int 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') {
            A[++cnta] = i - (cnta - 1);
        } else if (S[i] == 'G') {
            B[++cntb] = i - (cntb - 1);
        } else {
            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;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:41:15: warning: operation on 'cnta' may be undefined [-Wsequence-point]
   41 |             A[++cnta] = i - (cnta - 1);
      |               ^~~~~~
joi2019_ho_t3.cpp:41:15: warning: operation on 'cnta' may be undefined [-Wsequence-point]
joi2019_ho_t3.cpp:43:15: warning: operation on 'cntb' may be undefined [-Wsequence-point]
   43 |             B[++cntb] = i - (cntb - 1);
      |               ^~~~~~
joi2019_ho_t3.cpp:43:15: warning: operation on 'cntb' may be undefined [-Wsequence-point]
joi2019_ho_t3.cpp:45:15: warning: operation on 'cntc' may be undefined [-Wsequence-point]
   45 |             C[++cntc] = i - (cntc - 1);
      |               ^~~~~~
joi2019_ho_t3.cpp:45:15: warning: operation on 'cntc' may be undefined [-Wsequence-point]

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 68 ms 162912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -