Submission #145201

#	Time	Username	Problem	Language	Result	Execution time	Memory
145201		TadijaSebez	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	15 / 100	188 ms	4316 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int N=405;
const int inf=1e9+7;
int dp[3][N][N],tmp[3][N][N];
int pos[3][N],cnt[3];
char s[N];
void Clear(int a[3][N][N]){ for(int i=0;i<3;i++) for(int j=0;j<N;j++) for(int k=0;k<N;k++) a[i][j][k]=inf;}
void ckmn(int &a, int b){ a=min(a,b);}
int main()
{
	int n;
	scanf("%i",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='R') pos[0][++cnt[0]]=i;
		if(s[i]=='G') pos[1][++cnt[1]]=i;
		if(s[i]=='Y') pos[2][++cnt[2]]=i;
	}
	for(int i=0;i<3;i++) reverse(pos[i]+1,pos[i]+1+cnt[i]);
	Clear(dp);
	//printf("%i %i %i\n",cnt[0],cnt[1],cnt[2]);
	if(cnt[0]) dp[0][cnt[0]-1][cnt[1]]=pos[0][cnt[0]]-1;
	if(cnt[1]) dp[1][cnt[0]][cnt[1]-1]=pos[1][cnt[1]]-1;
	if(cnt[2]) dp[2][cnt[0]][cnt[1]]=pos[2][cnt[2]]-1;
	for(int i=2;i<=n;i++)
	{
		Clear(tmp);
		for(int f=0;f<3;f++)
			for(int r=0;r<=cnt[0];r++)
				for(int g=0;g<=cnt[1];g++) if(dp[f][r][g]!=inf)
				{
					int y=n-i-r-g+1;
					//printf("%i %i %i %i: %i\n",f,r,g,y,dp[f][r][g]);
                    if(f!=0 && r) ckmn(tmp[0][r-1][g],dp[f][r][g]+max(0,pos[0][r]-i));
                    if(f!=1 && g) ckmn(tmp[1][r][g-1],dp[f][r][g]+max(0,pos[1][g]-i));
                    if(f!=2 && y) ckmn(tmp[2][r][g],dp[f][r][g]+max(0,pos[2][y]-i));
				}
		for(int f=0;f<3;f++)
			for(int r=0;r<=cnt[0];r++)
				for(int g=0;g<=cnt[1];g++)
					dp[f][r][g]=tmp[f][r][g];
	}
	int ans=inf;
	for(int f=0;f<3;f++)
		for(int r=0;r<=cnt[0];r++)
			for(int g=0;g<=cnt[1];g++)
				ckmn(ans,dp[f][r][g]);
	printf("%i\n",ans==inf?-1:ans);
	return 0;
}

Compilation message (stderr)

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

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