제출 #1104871

#제출 시각아이디문제언어결과실행 시간메모리
1104871Champ_NamanGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
0 / 100
528 ms971804 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define nl '\n' int dp[401][401][401][3]; inline void solve(){ int n; cin>>n; string s; cin>>s; s = " "+s; int p[3][n+1], c[3]; for(int l=0; l<3; l++) for(int i=1; i<=n; i++) p[l][i] = -1; p[0][0] = p[1][0] = p[2][0] = c[0] = c[1] = c[2] = 0; for(int i=1; i<=n; i++){ if(s[i] == 'R') p[0][++c[0]] = i; else if(s[i] == 'G') p[1][++c[1]] = i; else p[2][++c[2]] = i; } for(int r=0; r<=n; r++) for(int g=0; g<=n; g++) for(int l=0; l<3; l++) dp[0][r][g][l] = 1e9; for(int l=0; l<3; l++) dp[0][0][0][l] = 0; for(int i=1; i<=n; i++){ for(int r=0; r<=i; r++){ for(int g=0; g<=i; g++){ int y = i - r - g; for(int l=0; l<3; l++){ if(y < 0 or (l == 0 ? r : (l == 1 ? g : y)) == 0){ dp[i][r][g][l] = 1e9; continue; } dp[i][r][g][l] = 1e9; if(l == 0) dp[i][r][g][l] = min(dp[i-1][r-1][g][1], dp[i-1][r-1][g][2]) + max(0LL, p[0][r] - i); if(l == 1) dp[i][r][g][l] = min(dp[i-1][r][g-1][0], dp[i-1][r][g-1][2]) + max(0LL, p[1][g] - i); if(l == 2) dp[i][r][g][l] = min(dp[i-1][r][g][0], dp[i-1][r][g][1]) + max(0LL, p[2][y] - i); } } } } int ans = min({dp[n][c[0]][c[1]][0], dp[n][c[0]][c[1]][1], dp[n][c[0]][c[1]][2]}); cout<<(ans >= 1e9 ? -1 : ans)<<nl; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); int t = 1; //cin>>t; while(t--) 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...