Submission #136786

#	Time	Username	Problem	Language	Result	Execution time	Memory
136786		hamzqq9	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	412 ms	268472 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 2000000000
#define N 3005
#define MOD 998244353
using namespace std;

int n;
int a[405];
int dp[405][205][205][4];
int shift[5][5][405][405];
int pos[5][405];
int tot[5];
char s[405];

int f(int cur,int cnt1,int cnt2,int last) {

	if(cur==n+1) return 0;

	int& r=dp[cur][cnt1][cnt2][last];

	if(~r) return r;

	r=inf;

	int cnt3=(cur-1-cnt1-cnt2);

	if(last!=1) {

		if(cnt1!=tot[1]) {

			int add=shift[1][2][cnt1+1][cnt2]+shift[1][3][cnt1+1][cnt3];

			umin(r,f(cur+1,cnt1+1,cnt2,1)+add);

		}

	}

	if(last!=2) {

		if(cnt2!=tot[2]) {

			int add=shift[2][1][cnt2+1][cnt1]+shift[2][3][cnt2+1][cnt3];

			umin(r,f(cur+1,cnt1,cnt2+1,2)+add);

		}

	}

	if(last!=3) {

		if(cnt3!=tot[3]) {

			int add=shift[3][1][cnt3+1][cnt1]+shift[3][2][cnt3+1][cnt2];

			umin(r,f(cur+1,cnt1,cnt2,3)+add);

		}

	}

	return r;

}

void pre() {

	for(int i=1;i<=n;i++) {
	
		a[i]=(s[i]=='R'?1:s[i]=='G'?2:3);
		
		++tot[a[i]];

		pos[a[i]][tot[a[i]]]=i;

	}

	for(int l1=1;l1<=3;l1++) {

		for(int l2=1;l2<=3;l2++) {

			if(l1==l2) continue ;

			for(int c1=0;c1<=tot[l1];c1++) {

				int cnt=0;

				for(int c2=0;c2<=tot[l2];c2++) {

					cnt+=(pos[l1][c1]<pos[l2][c2]);

					shift[l1][l2][c1][c2]=cnt;

				}

			}

		}

	}

}

void valid() {

	int cnt[99]={0};

	for(int i=1;i<=n;i++) {

		cnt[s[i]]++;

	}

	if(*max_element(cnt,cnt+99)>(n+1)/2) {

		printf("-1");

		exit(0);

	}

}

int main() {

	scanf("%d",&n);

	scanf("%s",s+1);

	valid();

	pre();

	memset(dp,-1,sizeof(dp));

 	printf("%d",f(1,0,0,0));

}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void valid()':
joi2019_ho_t3.cpp:122:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   cnt[s[i]]++;
           ^
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:138:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
joi2019_ho_t3.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~

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