Submission #391629

#	Time	Username	Problem	Language	Result	Execution time	Memory
391629		keta_tsimakuridze	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	92 ms	6664 KiB

joi2019_ho_t3

#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[2][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[0][j][k][0]=dp[0][j][k][1]=dp[0][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;
				dp[1][j][k][0]=dp[1][j][k][1]=dp[1][j][k][2]=mod;
				if(j) dp[1][j][k][0] =min(mod, min(dp[0][j-1][k][1],dp[0][j-1][k][2]) + kth[0][j] + aft[0][1][j][k] + aft[0][2][j][i-k-j] - i);
				if(k) dp[1][j][k][1] =min(mod, min(dp[0][j][k-1][2],dp[0][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[1][j][k][2] = min(mod,min(dp[0][j][k][1],dp[0][j][k][0]) + kth[2][i-j-k] + aft[2][0][i-j-k][j] + aft[2][1][i-j-k][k] - i);
			}
		}
		for(int j=0;j<=cnt[0];j++){
			for(int k=0;k<=cnt[1];k++){
				dp[0][j][k][0]=dp[1][j][k][0];
				dp[0][j][k][2]=dp[1][j][k][2];
				dp[0][j][k][1]=dp[1][j][k][1];
				
		}} 
	}
	int c = min(dp[0][cnt[0]][cnt[1]][0],min(dp[0][cnt[0]][cnt[1]][1],dp[0][cnt[0]][cnt[1]][2]));
	if(c==mod)cout<<-1;
	else cout<<c;
}

Compilation message (stderr)

joi2019_ho_t3.cpp:9:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 |  main(){
      |       ^

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25