| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 883039 | vjudge1 | Growing Vegetable is Fun 3 (JOI19_ho_t3) | C++14 | 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 int long long
const int inf = 1e9 + 7;
inline int eval(int x , int y){
return max(0 , x-y);
}
inline void ckmin(int &x , int y){
x = min(x,y);
}
void solve(){
int n;
cin >> n;
string str;
cin >> str;
vector < int > ind[3];
for(int i = 0;i<n;i++){
if(str[i] == 'R')ind[0].push_back(i);
else if(str[i] == 'G')ind[1].push_back(i);
else ind[2].push_back(i);
}
int dp[ind[0].size()+2][ind[1].size()+2][ind[2].size()+2][3];
for(int i = 0;i<=ind[0].size();i++){
for(int j = 0;j<=ind[1].size();j++){
for(int k = 0;k<=ind[2].size();k++){
dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = inf;
}
}
}
dp[0][0][0][0] = 0;
for(int cnt0 = 0;cnt0 <= (int)ind[0].size();cnt0++){
for(int cnt1 = 0;cnt1 <= (int)ind[1].size();cnt1++){
for(int cnt2 = 0;cnt2 <= (int)ind[2].size();cnt2++){
if(cnt0 != (int)ind[0].size()){
if(cnt0 == 0 and cnt1 == 0 and cnt2 == 0){
ckmin(dp[cnt0+1][cnt1][cnt2][0] , dp[cnt0][cnt1][cnt2][0] + eval(ind[0][cnt0] , cnt0+cnt1+cnt2));
}
ckmin(dp[cnt0+1][cnt1][cnt2][0] , dp[cnt0][cnt1][cnt2][1] + eval(ind[0][cnt0] , cnt0+cnt1+cnt2));
ckmin(dp[cnt0+1][cnt1][cnt2][0] , dp[cnt0][cnt1][cnt2][2] + eval(ind[0][cnt0] , cnt0+cnt1+cnt2));
}
if(cnt1 != (int)ind[1].size()){
ckmin(dp[cnt0][cnt1+1][cnt2][1] , dp[cnt0][cnt1][cnt2][0] + eval(ind[1][cnt1] , cnt0+cnt1+cnt2));
if(cnt0 == 0 and cnt1 == 0 and cnt2 == 0){
ckmin(dp[cnt0][cnt1+1][cnt2][1] , dp[cnt0][cnt1][cnt2][1] + eval(ind[1][cnt1] , cnt0+cnt1+cnt2));
}
ckmin(dp[cnt0][cnt1+1][cnt2][1] , dp[cnt0][cnt1][cnt2][2] + eval(ind[1][cnt1] , cnt0+cnt1+cnt2));
}
if(cnt2 != (int)ind[2].size()){
ckmin(dp[cnt0][cnt1][cnt2+1][2] , dp[cnt0][cnt1][cnt2][0] + eval(ind[2][cnt2] , cnt0+cnt1+cnt2));
ckmin(dp[cnt0][cnt1][cnt2+1][2] , dp[cnt0][cnt1][cnt2][1] + eval(ind[2][cnt2] , cnt0+cnt1+cnt2));
if(cnt0 == 0 and cnt1 == 0 and cnt2 == 0){
ckmin(dp[cnt0][cnt1][cnt2+1][2] , dp[cnt0][cnt1][cnt2][2] + eval(ind[2][cnt2] , cnt0+cnt1+cnt2));
}
}
}
}
}
int ans = inf;
for(int i = 0;i<3;i++){
ans = min(ans , dp[ind[0].size()][ind[1].size()][ind[2].size()][i]);
}
cout << (ans == inf ? -1 : ans) << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
}