답안 #136785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136785 2019-07-26T08:53:36 Z hamzqq9 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
221 ms 266908 KB
#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;

					cerr<<l1<<" "<<l2<<' '<<c1<<' '<<c2<<" "<< cnt<<'\n';

				}

			}

		}

	}

}

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

joi2019_ho_t3.cpp: In function 'void valid()':
joi2019_ho_t3.cpp:124:11: warning: array subscript has type 'char' [-Wchar-subscripts]
   cnt[s[i]]++;
           ^
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:140: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:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 220 ms 266908 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 220 ms 266908 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 221 ms 266776 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 220 ms 266908 KB Output isn't correct
2 Halted 0 ms 0 KB -