제출 #101716

#제출 시각아이디문제언어결과실행 시간메모리
101716KCSCGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++14
0 / 100
647 ms780648 KiB
#include <bits/stdc++.h> using namespace std; const int DIM = 405; const int INF = 405 * 405; int dp[DIM][DIM][DIM][3], idx[3]; int tot[3], psm[DIM][3], lst[DIM][3]; inline void f(int &x, int y) { if (x >= y) { x = y; } } int main(void) { #ifdef HOME freopen("vegetables.in", "r", stdin); freopen("vegetables.out", "w", stdout); #endif int n; cin >> n; for (int i = 1; i <= n; ++i) { char ch; cin >> ch; if (ch == 'R') { lst[++tot[0]][0] = i; ++psm[i][0]; } if (ch == 'G') { lst[++tot[1]][1] = i; ++psm[i][1]; } if (ch == 'Y') { lst[++tot[2]][2] = i; ++psm[i][2]; } for (int l = 0; l <= 2; ++l) { psm[i][l] += psm[i - 1][l]; } } memset(dp, 0x3f, sizeof dp); for (int l = 0; l <= 2; ++l) { dp[0][0][0][l] = 0; } for (int a = 0; a <= tot[0]; ++a) { for (int b = 0; b <= tot[1]; ++b) { for (int c = 0; c <= tot[2]; ++c) { for (int l = 0; l <= 2; ++l) { if (l != 0 and a < tot[0]) { int p = lst[a + 1][0]; f(dp[a + 1][b][c][0], dp[a][b][c][l] + max(0, psm[p][1] - b) + max(0, psm[p][2] - c)); } if (l != 1 and b < tot[1]) { int p = lst[b + 1][1]; f(dp[a][b + 1][c][1], dp[a][b][c][l] + max(0, psm[p][2] - c) + max(0, psm[p][0] - a)); } if (l != 2 and c < tot[2]) { int p = lst[c + 1][2]; f(dp[a][b][c + 1][2], dp[a][b][c][l] + max(0, psm[p][0] - a) + max(0, psm[p][1] - b)); } } } } } int v = min( { dp[tot[0]][tot[1]][tot[2]][0], dp[tot[0]][tot[1]][tot[2]][1], dp[tot[0]][tot[1]][tot[2]][2] } ); cout << (v >= INF ? -1 : v) << endl; 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...