| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 849113 | pudelos | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h> using namespace std; #define loop(_i, _a, _b) for(int _i=_a; _i<=_b; ++_i) const int maxn=401, maxn2=201, inf=1e9; int n; int cnt[4][maxn][4]; int dp[maxn2][maxn2][maxn2][4]; int val[maxn]; string s; int main() { cin.tie(0) -> ios_base::sync_with_stdio(0); cin >> n >> s; int a=0, b=0, c=0; loop(i, 1, n) { int v; if(s[i-1] == 'R') v=1; if(s[i-1] == 'G') v=2; if(s[i-1] == 'Y') v=3; val[i]=v; if(v==1) { ++a; cnt[1][a][2]=b; cnt[1][a][3]=c; } if(v==2) { ++b; cnt[2][b][1]=a; cnt[2][b][3]=c; } if(v==3) { ++c; cnt[3][c][1]=a; cnt[3][c][2]=b; } } // cout << a << ' ' << b << ' ' << c << '\n'; if(n/2+n%2 < max({a,b,c})) { cout << "-1"; return 0; } // vector<vector<vector<vector<int>>>> dp(a+1, vector<vector<vector<int>>>(b+1, vector<vector<int>>(c+1, vector<int>(4, inf)))); loop(i, 0, maxn2-1) loop(j, 0, maxn2-1) loop(k, 0, maxn2-1) loop(l, 1, 3) dp[i][j][k][l]=inf; // if()/ dp[0][0][0][1]=0; dp[0][0][0][2]=0; dp[0][0][0][3]=0; loop(i, 0, a) { loop(j, 0, b) { loop(k, 0, c) { if(i<a) dp[i+1][j][k][1]=min(dp[i+1][j][k][1], min(dp[i][j][k][2], dp[i][j][k][3])+max(cnt[1][i+1][2]-j, 0)+max(cnt[1][i+1][3])-k, 0); if(j<b) dp[i][j+1][k][2]=min(dp[i][j+1][k][2], min(dp[i][j][k][1], dp[i][j][k][3])+max(cnt[2][j+1][1]-i, 0)+max(cnt[2][j+1][3])-k, 0); if(k<c) dp[i][j][k+1][3]=min(dp[i][j][k+1][3], min(dp[i][j][k][1], dp[i][j][k][2])+max(cnt[3][k+1][1]-i, 0)+max(cnt[3][k+1][2])-j, 0); } } } int res = inf; loop(i, 1, 3) res=min(res, dp[a][b][c][i]); if(res==inf) cout << "-1"; else cout << res/2; }