Submission #171002

#	Time	Username	Problem	Language	Result	Execution time	Memory
171002		errorgorn	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	206 ms	101760 KiB

joi2019_ho_t3

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
char arr[405];
int pre[405][3];
vector<int> r,g,y;
int memo[205][205][205][3];
const int INF=1000000000;
int dp(int sr,int sg,int sy,int last){ ///1000000000 for invalid case
	if (!sr && !sg && !sy) return 0;
	else if (memo[sr][sg][sy][last]!=-1) return memo[sr][sg][sy][last];
	int ans=INF;
	if (last!=0 && sr) ans=min(ans,dp(sr-1,sg,sy,0)
		+max(0,pre[r[sr-1]][1]-sg)+max(0,pre[r[sr-1]][2]-sy));
	if (last!=1 && sg) ans=min(ans,dp(sr,sg-1,sy,1)
		+max(0,pre[g[sg-1]][0]-sr)+max(0,pre[g[sg-1]][2]-sy));
	if (last!=2 && sy) ans=min(ans,dp(sr,sg,sy-1,2)
		+max(0,pre[y[sy-1]][0]-sr)+max(0,pre[y[sy-1]][1]-sg));
	//printf("%d %d %d %d %d\n",sr,sg,sy,last,ans);
	return memo[sr][sg][sy][last]=ans;
}
int main(){
	//freopen("input.txt","r",stdin);
	scanf("%d",&n);
	getchar();
	for (int x=0;x<n;x++){
		arr[x]=getchar();
		if (arr[x]=='R') r.push_back(x);
		else if (arr[x]=='G') g.push_back(x);
		else y.push_back(x);
	}
	if (r.size()>200 || g.size()>200 || y.size()>200) {
		printf("-1\n");
		return 0;
	}
	for (int x=0;x<n;x++){
		if (arr[x]=='R') pre[x][0]++;
		else if (arr[x]=='G') pre[x][1]++;
		else pre[x][2]++;
		for (int y=0;y<3;y++) pre[x+1][y]=pre[x][y];
	}
	memset(memo,-1,sizeof(memo));
	int ans=INF;
	if (!r.empty()) ans=min(ans,dp(r.size()-1,g.size(),y.size(),0));
	if (!g.empty()) ans=min(ans,dp(r.size(),g.size()-1,y.size(),1));
	if (!y.empty()) ans=min(ans,dp(r.size(),g.size(),y.size()-1,2));
	printf("%d\n",(ans==INF)?-1:ans);
}

Compilation message (stderr)

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

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