| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 391591 | keta_tsimakuridze | 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>
#define f first
#define int long long
#define s second
using namespace std;
const int N=405,mod=1e16;
int t,dp[N][N][N][4],cnt[4],kth[4][N],aft[4][4][N][N],n;
string s;
main(){
// t=1;
cin >> n;
cin>>s;
s='#'+s;
for(int i=1;i<=n;i++){
if(s[i]=='R') s[i]='0';
else if(s[i]=='Y') s[i]='1';
else s[i]='2';
cnt[s[i]-'0']++;
kth[s[i]-'0'][cnt[s[i]-'0']] = i;
}
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
if(i==j) continue;
for(int k=0;k<=cnt[i];k++){
for(int k1=1;k1<=cnt[j];k1++){
aft[i][j][k][k1] = aft[i][j][k][k1-1] + (kth[j][k1] > kth[i][k]);
}
}
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<=cnt[0];j++){
for(int k=0;k<=cnt[1];k++){
dp[i][j][k][0]=dp[i][j][k][1]=dp[i][j][k][2]=mod;
}} }
dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=cnt[0];j++){
for(int k=0;k<=cnt[1];k++){
if(i-k-j>cnt[2]) continue;
if(j) dp[i][j][k][0] = min(dp[i-1][j-1][k][1],dp[i-1][j-1][k][2]) + kth[0][j] + aft[0][1][j][k] + aft[0][2][j][i-k-j] - i;
if(k) dp[i][j][k][1] = min(dp[i-1][j][k-1][2],dp[i-1][j][k-1][0]) + kth[1][k] + aft[1][0][k][j] + aft[1][2][k][i-k-j] - i;
if(i-j-k) dp[i][j][k][2] = min(dp[i-1][j][k][1],dp[i-1][j][k][0]) + kth[2][i-j-k] + aft[2][0][i-j-k][j] + aft[2][1][i-j-k][k] - i;
}
}
}
int c = min(dp[n][cnt[0]][cnt[1]][0],min(dp[n][cnt[0]][cnt[1]][1],dp[n][cnt[0]][cnt[1]][2]));
if(c==mod)cout<<-1;
else cout<<c;
}