Submission #716385

#TimeUsernameProblemLanguageResultExecution timeMemory
716385KahouGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
393 ms780492 KiB
/* In the name of God, aka Allah */ #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") #include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' #define mk make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = 405; int n, dp[N][N][N][3]; string s; vector<int> vc[3]; pii vt[3][N]; void solve() { cin >> n; cin >> s; s = '.'+s; for (int i = 1; i <= n; i++) { int c = (s[i] != 'R') + (s[i] == 'Y'); vc[c].push_back(i); } int a, b, c; b = 0, c = 0; for (int A = 0; A < (int)vc[0].size(); A++) { while (b < (int)vc[1].size() && vc[1][b] < vc[0][A]) b++; while (c < (int)vc[2].size() && vc[2][c] < vc[0][A]) c++; vt[0][A] = {b, c}; } a = 0, c = 0; for (int B = 0; B < (int)vc[1].size(); B++) { while (a < (int)vc[0].size() && vc[0][a] < vc[1][B]) a++; while (c < (int)vc[2].size() && vc[2][c] < vc[1][B]) c++; vt[1][B] = {a, c}; } a = 0, b = 0; for (int C = 0; C < (int)vc[2].size(); C++) { while (a < (int)vc[0].size() && vc[0][a] < vc[2][C]) a++; while (b < (int)vc[1].size() && vc[1][b] < vc[2][C]) b++; vt[2][C] = {a, b}; } memset(dp, 64, sizeof dp); dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0; for (int sum = 0; sum < n; sum++) { for (int A = 0; A <= min(sum, (int)vc[0].size()); A++) { for (int B = 0; B <= min(sum-A, (int)vc[1].size()); B++) { int C = sum-A-B; if (A < (int)vc[0].size()) { int b = vt[0][A].F; int c = vt[0][A].S; dp[A+1][B][C][0] = min(dp[A+1][B][C][0], min(dp[A][B][C][1], dp[A][B][C][2]) + vc[0][A]+max(B-b, 0)+max(C-c, 0)-(A+B+C+1)); } if (B < (int)vc[1].size()) { int a = vt[1][B].F; int c = vt[1][B].S; dp[A][B+1][C][1] = min(dp[A][B+1][C][1], min(dp[A][B][C][0], dp[A][B][C][2]) + vc[1][B]+max(A-a, 0)+max(C-c, 0)-(A+B+C+1)); } if (C < (int)vc[2].size()) { int a = vt[2][C].F; int b = vt[2][C].S; dp[A][B][C+1][2] = min(dp[A][B][C+1][2], min(dp[A][B][C][0], dp[A][B][C][1]) + vc[2][C]+max(A-a,0)+max(B-b, 0)-(A+B+C+1)); } } } } int ans = 1e9; ans = min(dp[vc[0].size()][vc[1].size()][vc[2].size()][0], ans); ans = min(dp[vc[0].size()][vc[1].size()][vc[2].size()][1], ans); ans = min(dp[vc[0].size()][vc[1].size()][vc[2].size()][2], ans); cout << (ans >= 1e9? -1 : ans) << endl; } int main() { ios::sync_with_stdio(0), cin.tie(0); solve(); 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...