Submission #1034932

#TimeUsernameProblemLanguageResultExecution timeMemory
1034932ten_xdGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
75 / 100
508 ms763380 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; #define rep(a,b) for(int a = 0; a < (b); ++a) #define all(t) t.begin(), t.end() #define pb push_back const int N = 402, INF = 2e9+54321; const ll INF_L = (ll)2e18+54321; int n; string A; int B[N]; int S[3][N]; vector<int> V[3]; int dp[N][N][N][3]; void solve() { cin >> n >> A; rep(i,n) { if(A[i] == 'R') B[i] = 0; else if(A[i] == 'Y') B[i] = 1; else B[i] = 2; } rep(i,3) { int s = 0; rep(j,n) { S[i][j] = s; if(B[j] == i) ++s; } } rep(i,n) V[B[i]].pb(i); rep(i,N) rep(j,N) rep(k,N) rep(f,3) dp[i][j][k][f] = INF; if((int)V[0].size() > 0) dp[1][1][0][0] = V[0][0]; if((int)V[1].size() > 0) dp[1][0][1][1] = V[1][0]; if((int)V[2].size() > 0) dp[1][0][0][2] = V[2][0]; for(int i = 1; i < n; ++i) { for(int A = 0; A <= i; ++A) { for(int B = 0; B <= i-A; ++B) { int C = i-A-B; int W[3]; W[0] = A, W[1] = B, W[2] = C; rep(k,3) { rep(f,3) { if(k == f or (int)V[f].size() <= W[f]) continue; int idx = V[f][W[f]], poz = 0; poz = idx + (max(0,W[0]-S[0][idx])) + (max(0,W[1]-S[1][idx])) + (max(0,W[2]-S[2][idx])); int H[3]; H[0] = W[0], H[1] = W[1], H[2] = W[2], ++H[f]; int cost = dp[i][W[0]][W[1]][k]+(poz-i); dp[i+1][H[0]][H[1]][f] = min(dp[i+1][H[0]][H[1]][f],cost); } } } } } int wyn = INF; rep(i,N) rep(j,N) rep(k,3) wyn = min(wyn,dp[n][i][j][k]); if(wyn >= INF) cout << "-1" << '\n'; else cout << wyn << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); 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...