Submission #410257

#TimeUsernameProblemLanguageResultExecution timeMemory
410257ngpin04Growing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
97 ms162912 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair using namespace std; const int N = 405; const int oo = 1e9; vector <int> pos[3]; int dp[N][N][N][4]; int cnt[N][3]; int sz[3]; int n; template <typename T> void mini(T &a, T b) { if (a > b) a = b; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { char c; cin >> c; int val = 2; if (c == 'R') val = 0; if (c == 'G') val = 1; pos[val].push_back(i); cnt[i][val]++; } for (int i = 1; i <= n; i++) for (int j = 0; j < 3; j++) cnt[i][j] += cnt[i - 1][j]; for (int i = 0; i < 3; i++) sz[i] = pos[i].size(); for (int i = 0; i <= sz[0]; i++) for (int j = 0; j <= sz[1]; j++) for (int k = 0; k <= sz[2]; k++) for (int pre = 0; pre < 3; pre++) if (i || j || k) dp[i][j][k][pre] = oo; for (int i = 0; i <= sz[0]; i++) for (int j = 0; j <= sz[1]; j++) for (int k = 0; k <= sz[2]; k++) for (int pre = 0; pre < 3; pre++) if (dp[i][j][k][pre] < oo) { int cur = dp[i][j][k][pre]; int x = i + j + k + 1; if (i < sz[0] && pre != 0) { int posval = pos[0][i]; if (j > 0) posval += max(0, cnt[pos[1][j - 1]][1] - cnt[pos[0][i]][1]); if (k > 0) posval += max(0, cnt[pos[2][k - 1]][2] - cnt[pos[0][i]][2]); mini(dp[i + 1][j][k][0], cur + posval - x); } if (j < sz[1] && pre != 1) { int posval = pos[1][j]; if (i > 0) posval += max(0, cnt[pos[0][i - 1]][0] - cnt[pos[1][j]][0]); if (k > 0) posval += max(0, cnt[pos[2][k - 1]][2] - cnt[pos[1][j]][2]); mini(dp[i][j + 1][k][1], cur + posval - x); } if (k < sz[2] && pre != 2) { int posval = pos[2][k]; if (j > 0) posval += max(0, cnt[pos[1][j - 1]][1] - cnt[pos[2][k]][1]); if (i > 0) posval += max(0, cnt[pos[0][i - 1]][0] - cnt[pos[2][k]][0]); mini(dp[i][j][k + 1][2], cur + posval - x); } } int ans = oo; for (int i = 0; i < 3; i++) ans = min(ans, dp[sz[0]][sz[1]][sz[2]][i]); if (ans == oo) ans = -1; cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...