Submission #929843

#	Time	Username	Problem	Language	Result	Execution time	Memory
929843		beepbeepsheep	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	141 ms	779916 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

#define ll short
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>

const short maxn=405;
const short inf=10000;

short dp[maxn][maxn][maxn][4];
short cost[maxn][maxn][maxn][4];
vector<short> r,g,y;
short suff[410];
short solve(short a, short b, short c, short flag){
	if (a<0 || b<0 || c<0) return inf;
	if (a==0 && b==0 && c==0) return 0;
	if (dp[a][b][c][flag]!=-1) return dp[a][b][c][flag];
	if (flag==1){
		dp[a][b][c][flag] = min(solve(a-1,b,c,2),solve(a-1,b,c,3));
	}
	if (flag==2){
		dp[a][b][c][flag] = min(solve(a,b-1,c,1),solve(a,b-1,c,3));
	}
	if (flag==3){
		dp[a][b][c][flag] = min(solve(a,b,c-1,1),solve(a,b,c-1,2));
	}
	dp[a][b][c][flag]+=cost[a][b][c][flag];
	return dp[a][b][c][flag];
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	short n;
	cin>>n;
	string s;
	cin>>s;
	for (short i=1;i<=n;i++){
		if (s[i-1]=='R') r.emplace_back(i);
		if (s[i-1]=='Y') y.emplace_back(i);
		if (s[i-1]=='G') g.emplace_back(i);
	}
	if (2*max({r.size(),g.size(),y.size()})>n+(n&1)){
		cout<<-1;
		return 0;
	}
	for (int i=0;i<=r.size();i++){
		for (int j=0;j<=g.size();j++){
			//create suffix sum array
			memset(suff,0,sizeof(suff));
			for (int k=0;k<i;k++) suff[r[k]]=1;
			for (int k=0;k<j;k++) suff[g[k]]=1;
			for (int k=405;k>=0;k--) suff[k]+=suff[k+1];
			for (int k=0;k<y.size();k++){
				cost[i][j][k+1][3]=abs((suff[y[k]]+y[k])-(i+j+k+1));
			}
		}
	}
	for (int i=0;i<=g.size();i++){
		for (int j=0;j<=y.size();j++){
			//create suffix sum array
			memset(suff,0,sizeof(suff));
			for (int k=0;k<i;k++) suff[g[k]]=1;
			for (int k=0;k<j;k++) suff[y[k]]=1;
			for (int k=405;k>=0;k--) suff[k]+=suff[k+1];
			for (int k=0;k<r.size();k++){
				cost[k+1][i][j][1]=abs((suff[r[k]]+r[k])-(i+j+k+1));
			}
		}
	}
	for (int i=0;i<=y.size();i++){
		for (int j=0;j<=r.size();j++){
			//create suffix sum array
			memset(suff,0,sizeof(suff));
			for (int k=0;k<i;k++) suff[y[k]]=1;
			for (int k=0;k<j;k++) suff[r[k]]=1;
			for (int k=405;k>=0;k--) suff[k]+=suff[k+1];
			for (int k=0;k<g.size();k++){
				cost[j][k+1][i][2]=abs((suff[g[k]]+g[k])-(i+j+k+1));
			}
		}
	}
	memset(dp,-1,sizeof(dp));
	cout<<min({solve(r.size(),g.size(),y.size(),1),
				solve(r.size(),g.size(),y.size(),2),
				solve(r.size(),g.size(),y.size(),3)});
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:43:41: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   43 |  if (2*max({r.size(),g.size(),y.size()})>n+(n&1)){
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
joi2019_ho_t3.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i=0;i<=r.size();i++){
      |               ~^~~~~~~~~~
joi2019_ho_t3.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int j=0;j<=g.size();j++){
      |                ~^~~~~~~~~~
joi2019_ho_t3.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for (int k=0;k<y.size();k++){
      |                 ~^~~~~~~~~
joi2019_ho_t3.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i=0;i<=g.size();i++){
      |               ~^~~~~~~~~~
joi2019_ho_t3.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int j=0;j<=y.size();j++){
      |                ~^~~~~~~~~~
joi2019_ho_t3.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for (int k=0;k<r.size();k++){
      |                 ~^~~~~~~~~
joi2019_ho_t3.cpp:71:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i=0;i<=y.size();i++){
      |               ~^~~~~~~~~~
joi2019_ho_t3.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (int j=0;j<=r.size();j++){
      |                ~^~~~~~~~~~
joi2019_ho_t3.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for (int k=0;k<g.size();k++){
      |                 ~^~~~~~~~~

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