Submission #545029

#	Time	Username	Problem	Language	Result	Execution time	Memory
545029		MilosMilutinovic	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	75 / 100	511 ms	89700 KiB

joi2019_ho_t3

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmin(T&x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T&x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,dp[405][405][405][3];
char s[405];
vector<int> pos[3];

int get(int x,int R,int p){
	if(R<0) return 0;
	if(pos[x][0]>p) return R+1;
	int l=0,r=R,t=0;
	while(l<=r){
		int m=(l+r)/2;
		if(pos[x][m]<=p) t=m,l=m+1; else r=m-1;
	}
	return R-t;
}

int main(){
	n=readint();
	scanf("%s",s);
	for(int i=0;i<n;i++){
		if(s[i]=='R') s[i]='A';
		if(s[i]=='Y') s[i]='B';
		if(s[i]=='G') s[i]='C';
		pos[s[i]-'A'].pb(i);
	}
	int ans=1e9,szA=pos[0].size(),szB=pos[1].size(),szC=pos[2].size();
	for(int i=0;i<=szA;i++)
		for(int j=0;j<=szB;j++)
			for(int k=0;k<=szC;k++)
				for(int p=0;p<3;p++)
					dp[i][j][k][p]=(i+j+k==0?0:1e9);
	for(int i=0;i<=szA;i++){
		for(int j=0;j<=szB;j++){
			for(int k=0;k<=szC;k++){
				for(int l=0;l<3;l++){
					if(i<szA&&l!=0){
						int p=pos[0][i]+get(0,i-1,pos[0][i])+get(1,j-1,pos[0][i])+get(2,k-1,pos[0][i]);
						chkmin(dp[i+1][j][k][0],dp[i][j][k][l]+p-i-j-k);
					}
					if(j<szB&&l!=1){
						int p=pos[1][j]+get(0,i-1,pos[1][j])+get(1,j-1,pos[1][j])+get(2,k-1,pos[1][j]);
						chkmin(dp[i][j+1][k][1],dp[i][j][k][l]+p-i-j-k);
					}
					if(k<szC&&l!=2){
						int p=pos[2][k]+get(0,i-1,pos[2][k])+get(1,j-1,pos[2][k])+get(2,k-1,pos[2][k]);
						chkmin(dp[i][j][k+1][2],dp[i][j][k][l]+p-i-j-k);
					}
				}
			}
		}
	}
	for(int i=0;i<3;i++)ans=min(ans,dp[szA][szB][szC][i]);
	printf("%d",(ans==1e9?-1:ans));
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%s",s);
      |  ~~~~~^~~~~~~~

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