oj.uz

Submission #952862

# Submission time Handle Problem Language Result Execution time Memory
952862 2024-03-25T03:38:27 Z offlineDeletionTrickFan Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 404;
int dp[MAXN][MAXN][MAXN][3], pos[3][MAXN], v[MAXN], cnt[3], pref[3][MAXN];
signed main() {
    int n;
    string s;
    cin >> n >> s;
    memset(dp, '?', sizeof dp), memset(pos, 0, sizeof pos), memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; ++i) {
        v[i] = s[i - 1] == 'R' ? 0 : s[i - 1] == 'G' ? 1 : 2;
        pref[0][i] = pref[0][i - 1] + (v[i] == 0);
        pref[1][i] = pref[1][i - 1] + (v[i] == 1);
        pref[2][i] = pref[2][i - 1] + (v[i] == 2);
        pos[v[i]][++cnt[v[i]]] = i;
    }
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for (int red = 0; red <= cnt[0]; ++red) {
        for (int green = 0; green <= cnt[1]; ++green) {
            for (int blue = 0; blue <= cnt[2]; ++blue) {
                if (red) dp[red][green][blue][0] = min(dp[red - 1][green][blue][1], dp[red - 1][green][blue][2]) + max(0LL, pref[1][pos[0][red]] - green) + max(0LL, pref[2][pos[0][red]] - blue);
                if (green) dp[red][green][blue][1] = min(dp[red][green - 1][blue][0], dp[red][green - 1][blue][2]) + max(0LL, pref[0][pos[1][green]] - red) + max(0LL, pref[2][pos[1][green]] - blue);
                if (blue) dp[red][green][blue][2] = min(dp[red][green][blue - 1][0], dp[red][green][blue - 1][1]) + max(0LL, pref[0][pos[2][blue]] - red) + max(0LL, pref[1][pos[2][blue]] - green);
            }
        }
    }
    int ans = *min_element(dp[cnt[0]][cnt[1]][cnt[2]], dp[cnt[0]][cnt[1]][cnt[2]] + 3);
    if (ans > n * n) cout << -1;
    else cout << ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1109 ms 933772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1109 ms 933772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 547 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1109 ms 933772 KB Time limit exceeded
2 Halted 0 ms 0 KB -