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 int long long
#define nl '\n'
vector<vector<vector<vector<int>>>> dp(401, vector<vector<vector<int>>>(401, vector<vector<int>>(401, vector<int>(3, 1e9))));
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++){
p[l][0] = 0;
c[l] = 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 l=0; l<3; l++) dp[0][0][0][l] = 0;
for(int i=1; i<=n; i++){
for(int r=0; r<=min(c[0], i); r++){
for(int g=0; g<=min(c[1], i-r); g++){
int y = i - r - g;
if(y > c[2]) continue;
if(r > 0) dp[i][r][g][0] = min(dp[i-1][r-1][g][1], dp[i-1][r-1][g][2]) + max(0LL, p[0][r] - i);
if(g > 0) dp[i][r][g][1] = min(dp[i-1][r][g-1][0], dp[i-1][r][g-1][2]) + max(0LL, p[1][g] - i);
if(y > 0) dp[i][r][g][2] = 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |