답안 #145205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
145205	2019-08-19T09:23:20 Z	TadijaSebez	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	75 / 100	500 ms	70204 KB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int N=405;
const int inf=1e9+7;
//int dp[3][N][N],tmp[3][N][N];
int pos[3][N],cnt[3];
char s[N];
void Clear(int a[3][N][N]){ for(int i=0;i<3;i++) for(int j=0;j<N;j++) for(int k=0;k<N;k++) a[i][j][k]=inf;}
void ckmn(int &a, int b){ a=min(a,b);}
int dp[3][N][N][N],val[3][N][N][N];
bool was[3][N][N][N];
int Get(int r, int g, int y, int f)
{
	int z;
	if(f==0) z=pos[0][r];
	if(f==1) z=pos[1][g];
	if(f==2) z=pos[2][y];
	int ans=0;
	for(int i=0;i<3;i++) if(i!=f)
	{
		int p=i==0?r:i==1?g:y;
		for(int j=cnt[i];j>p;j--) if(pos[i][j]<z) ans++;
	}
	return ans;
	/*if(f==0)
	{
		if(g!=cnt[1]) val[f][r][g][y]=val[f][r][g+1][y]+(pos[0][r]>pos[1][g+1]);
		else if(y!=cnt[2]) val[f][r][g][y]=val[f][r][g][y+1]+(pos[0][r]>pos[2][y+1]);
		else val[f][r][g][y]=0;
	}
	if(f==1)
	{
		if(r!=cnt[0]) val[f][r][g][y]=val[f][r+1][g][y]+(pos[1][g]>pos[0][r+1]);
		else if(y!=cnt[2]) val[f][r][g][y]=val[f][r][g][y+1]+(pos[1][g]>pos[2][y+1]);
		else val[f][r][g][y]=0;
	}
	if(f==2)
	{
		if(g!=cnt[1]) val[f][r][g][y]=val[f][r][g+1][y]+(pos[2][y]>pos[1][g+1]);
		else if(r!=cnt[0]) val[f][r][g][y]=val[f][r+1][g][y]+(pos[2][y]>pos[0][r+1]);
		else val[f][r][g][y]=0;
	}
	return val[f][r][g][y];*/
}
int Solve(int r, int g, int y, int f)
{
	if(was[f][r][g][y]) return dp[f][r][g][y];
	was[f][r][g][y]=1;
	dp[f][r][g][y]=inf;
	int i=r+g+y;
	if(i==0) return dp[f][r][g][y]=0;
	if(f!=0 && r) ckmn(dp[f][r][g][y],Solve(r-1,g,y,0)+Get(r,g,y,0));
	if(f!=1 && g) ckmn(dp[f][r][g][y],Solve(r,g-1,y,1)+Get(r,g,y,1));
	if(f!=2 && y) ckmn(dp[f][r][g][y],Solve(r,g,y-1,2)+Get(r,g,y,2));
	return dp[f][r][g][y];
}
int main()
{
	int n;
	scanf("%i",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='R') pos[0][++cnt[0]]=i;
		if(s[i]=='G') pos[1][++cnt[1]]=i;
		if(s[i]=='Y') pos[2][++cnt[2]]=i;
	}
	//for(int i=0;i<3;i++) reverse(pos[i]+1,pos[i]+1+cnt[i]);
	int ans=min(Solve(cnt[0],cnt[1],cnt[2],0),Solve(cnt[0],cnt[1],cnt[2],1));
	printf("%i\n",ans==inf?-1:ans);
	/*Clear(dp);
	//printf("%i %i %i\n",cnt[0],cnt[1],cnt[2]);
	if(cnt[0]) dp[0][cnt[0]-1][cnt[1]]=pos[0][cnt[0]]-1;
	if(cnt[1]) dp[1][cnt[0]][cnt[1]-1]=pos[1][cnt[1]]-1;
	if(cnt[2]) dp[2][cnt[0]][cnt[1]]=pos[2][cnt[2]]-1;
	for(int i=2;i<=n;i++)
	{
		Clear(tmp);
		for(int f=0;f<3;f++)
			for(int r=0;r<=cnt[0];r++)
				for(int g=0;g<=cnt[1];g++) if(dp[f][r][g]!=inf)
				{
					int y=n-i-r-g+1;
					//printf("%i %i %i %i: %i\n",f,r,g,y,dp[f][r][g]);
					if(f!=0 && r) ckmn(tmp[0][r-1][g],dp[f][r][g]+max(0,pos[0][r]-i));
					if(f!=1 && g) ckmn(tmp[1][r][g-1],dp[f][r][g]+max(0,pos[1][g]-i));
					if(f!=2 && y) ckmn(tmp[2][r][g],dp[f][r][g]+max(0,pos[2][y]-i));
				}
		for(int f=0;f<3;f++)
			for(int r=0;r<=cnt[0];r++)
				for(int g=0;g<=cnt[1];g++)
					dp[f][r][g]=tmp[f][r][g];
	}
	int ans=inf;
	for(int f=0;f<3;f++) ckmn(ans,dp[f][0][0]);
	printf("%i\n",ans==inf?-1:ans);*/
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
joi2019_ho_t3.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int Get(int, int, int, int)':
joi2019_ho_t3.cpp:22:29: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   for(int j=cnt[i];j>p;j--) if(pos[i][j]<z) ans++;
                             ^~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	632 KB	Output is correct
6	Correct	2 ms	760 KB	Output is correct
7	Correct	2 ms	680 KB	Output is correct
8	Correct	2 ms	632 KB	Output is correct
9	Correct	2 ms	632 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	632 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	632 KB	Output is correct
15	Correct	2 ms	636 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct

Subtask #2
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	632 KB	Output is correct
6	Correct	2 ms	760 KB	Output is correct
7	Correct	2 ms	680 KB	Output is correct
8	Correct	2 ms	632 KB	Output is correct
9	Correct	2 ms	632 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	632 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	632 KB	Output is correct
15	Correct	2 ms	636 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	7 ms	3448 KB	Output is correct
19	Correct	6 ms	2936 KB	Output is correct
20	Correct	6 ms	3320 KB	Output is correct
21	Correct	7 ms	3576 KB	Output is correct
22	Correct	5 ms	2680 KB	Output is correct
23	Correct	6 ms	3192 KB	Output is correct
24	Correct	5 ms	2296 KB	Output is correct
25	Correct	3 ms	1400 KB	Output is correct
26	Correct	3 ms	1656 KB	Output is correct
27	Correct	6 ms	3576 KB	Output is correct
28	Correct	6 ms	3576 KB	Output is correct
29	Correct	6 ms	3320 KB	Output is correct
30	Correct	7 ms	3320 KB	Output is correct
31	Correct	6 ms	2936 KB	Output is correct
32	Correct	6 ms	3448 KB	Output is correct
33	Correct	4 ms	1784 KB	Output is correct
34	Correct	4 ms	2040 KB	Output is correct
35	Correct	6 ms	3576 KB	Output is correct
36	Correct	5 ms	2808 KB	Output is correct
37	Correct	5 ms	2552 KB	Output is correct
38	Correct	5 ms	2936 KB	Output is correct
39	Correct	7 ms	3448 KB	Output is correct
40	Correct	2 ms	504 KB	Output is correct
41	Correct	3 ms	1272 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	6 ms	5032 KB	Output is correct
3	Correct	6 ms	4984 KB	Output is correct
4	Correct	6 ms	4984 KB	Output is correct
5	Correct	6 ms	4984 KB	Output is correct
6	Correct	6 ms	4984 KB	Output is correct
7	Correct	6 ms	4984 KB	Output is correct
8	Correct	6 ms	4984 KB	Output is correct
9	Correct	6 ms	4984 KB	Output is correct
10	Correct	7 ms	4984 KB	Output is correct
11	Correct	6 ms	5112 KB	Output is correct
12	Correct	4 ms	2808 KB	Output is correct
13	Correct	5 ms	3576 KB	Output is correct
14	Correct	5 ms	4216 KB	Output is correct
15	Correct	6 ms	4984 KB	Output is correct
16	Correct	6 ms	4984 KB	Output is correct

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	504 KB	Output is correct
5	Correct	2 ms	632 KB	Output is correct
6	Correct	2 ms	760 KB	Output is correct
7	Correct	2 ms	680 KB	Output is correct
8	Correct	2 ms	632 KB	Output is correct
9	Correct	2 ms	632 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	632 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	632 KB	Output is correct
15	Correct	2 ms	636 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	7 ms	3448 KB	Output is correct
19	Correct	6 ms	2936 KB	Output is correct
20	Correct	6 ms	3320 KB	Output is correct
21	Correct	7 ms	3576 KB	Output is correct
22	Correct	5 ms	2680 KB	Output is correct
23	Correct	6 ms	3192 KB	Output is correct
24	Correct	5 ms	2296 KB	Output is correct
25	Correct	3 ms	1400 KB	Output is correct
26	Correct	3 ms	1656 KB	Output is correct
27	Correct	6 ms	3576 KB	Output is correct
28	Correct	6 ms	3576 KB	Output is correct
29	Correct	6 ms	3320 KB	Output is correct
30	Correct	7 ms	3320 KB	Output is correct
31	Correct	6 ms	2936 KB	Output is correct
32	Correct	6 ms	3448 KB	Output is correct
33	Correct	4 ms	1784 KB	Output is correct
34	Correct	4 ms	2040 KB	Output is correct
35	Correct	6 ms	3576 KB	Output is correct
36	Correct	5 ms	2808 KB	Output is correct
37	Correct	5 ms	2552 KB	Output is correct
38	Correct	5 ms	2936 KB	Output is correct
39	Correct	7 ms	3448 KB	Output is correct
40	Correct	2 ms	504 KB	Output is correct
41	Correct	3 ms	1272 KB	Output is correct
42	Correct	2 ms	376 KB	Output is correct
43	Correct	6 ms	5032 KB	Output is correct
44	Correct	6 ms	4984 KB	Output is correct
45	Correct	6 ms	4984 KB	Output is correct
46	Correct	6 ms	4984 KB	Output is correct
47	Correct	6 ms	4984 KB	Output is correct
48	Correct	6 ms	4984 KB	Output is correct
49	Correct	6 ms	4984 KB	Output is correct
50	Correct	6 ms	4984 KB	Output is correct
51	Correct	7 ms	4984 KB	Output is correct
52	Correct	6 ms	5112 KB	Output is correct
53	Correct	4 ms	2808 KB	Output is correct
54	Correct	5 ms	3576 KB	Output is correct
55	Correct	5 ms	4216 KB	Output is correct
56	Correct	6 ms	4984 KB	Output is correct
57	Correct	6 ms	4984 KB	Output is correct
58	Execution timed out	1084 ms	70204 KB	Time limit exceeded
59	Halted	0 ms	0 KB	-

답안 #145205

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 55.0 / 55.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
55.0 / 55.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 25.0