Submission #481427

#TimeUsernameProblemLanguageResultExecution timeMemory
481427LoboGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
75 / 100
544 ms1009924 KiB
#include <bits/stdc++.h> using namespace std; const long long INFll = (long long) 1e18 + 10; const int INFii = (int) 1e9 + 10; typedef long long ll; typedef int ii; typedef long double dbl; #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define maxn 401 ii n, dp[maxn][maxn][maxn][4]; ii qtd1, qtd2, qtd3; ii pos1[maxn], pos2[maxn], pos3[maxn]; ii cnt1[maxn], cnt2[maxn], cnt3[maxn]; string s; ii sol(ii c1, ii c2, ii c3, ii ant) { if(dp[c1][c2][c3][ant] != -1) return dp[c1][c2][c3][ant]; ii ans = INFii; if(c1 != qtd1 && ant != 1) { ans = min(ans, sol(c1+1,c2,c3,1) + max(0,cnt2[pos2[c2]]-cnt2[pos1[c1+1]]) + max(0,cnt3[pos3[c3]]-cnt3[pos1[c1+1]])); } if(c2 != qtd2 && ant != 2) { ans = min(ans, sol(c1,c2+1,c3,2) + max(0,cnt1[pos1[c1]]-cnt1[pos2[c2+1]]) + max(0,cnt3[pos3[c3]]-cnt3[pos2[c2+1]])); } if(c3 != qtd3 && ant != 3) { ans = min(ans, sol(c1,c2,c3+1,3) + max(0,cnt2[pos2[c2]]-cnt2[pos3[c3+1]]) + max(0,cnt1[pos1[c1]]-cnt1[pos3[c3+1]])); } return dp[c1][c2][c3][ant] = ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); //freopen("in.in", "r", stdin); //freopen("out.out", "w", stdout); cin >> n >> s; for(ii i = 1; i <= n; i++) { cnt1[i] = cnt1[i-1]; cnt2[i] = cnt2[i-1]; cnt3[i] = cnt3[i-1]; if(s[i-1] == 'R') { cnt1[i]++; pos1[++qtd1] = i; } if(s[i-1] == 'G') { cnt2[i]++; pos2[++qtd2] = i; } if(s[i-1] == 'Y') { cnt3[i]++; pos3[++qtd3] = i; } } for(ii i = 0; i <= n; i++) { for(ii j = 0; j <= n; j++) { for(ii k = 0; k <= n; k++) { dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = dp[i][j][k][3] = -1; } } } if(qtd1 > (n+1)/2 || qtd2 > (n+1)/2 || qtd3 > (n+1)/2) { cout << -1 << endl; return 0; } dp[qtd1][qtd2][qtd3][0] = dp[qtd1][qtd2][qtd3][1] = dp[qtd1][qtd2][qtd3][2] = dp[qtd1][qtd2][qtd3][3] = 0; cout << sol(0,0,0,0) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...