Submission #117834

#	Time	Username	Problem	Language	Result	Execution time	Memory
117834		errorgorn	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	93 ms	101624 KiB

joi2019_ho_t3

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
char arr[405];
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,pos=sr+sg+sy-1;
	if (last!=0 && sr) ans=min(ans,dp(sr-1,sg,sy,0)+abs(pos-r[sr-1]));
	if (last!=1 && sg) ans=min(ans,dp(sr,sg-1,sy,1)+abs(pos-g[sg-1]));
	if (last!=2 && sy) ans=min(ans,dp(sr,sg,sy-1,2)+abs(pos-y[sy-1]));
	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);
	}
	memset(memo,-1,sizeof(memo));
	int ans=INF;
	if (!r.empty()) ans=min(ans,dp(r.size()-1,g.size(),y.size(),0)+abs(n-1-r.back()));
	if (!g.empty()) ans=min(ans,dp(r.size(),g.size()-1,y.size(),1)+abs(n-1-g.back()));
	if (!y.empty()) ans=min(ans,dp(r.size(),g.size(),y.size()-1,2)+abs(n-1-y.back()));
	printf("%d\n",(ans==INF)?-1:(ans>>1));
}

Compilation message (stderr)

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

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