oj.uz

Submission #545029

# Submission time Handle Problem Language Result Execution time Memory
545029 2022-04-03T10:49:58 Z MilosMilutinovic Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
75 / 100
 500 ms 89700 KB 
#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmin(T&x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T&x,T y){return x<y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,dp[405][405][405][3];
char s[405];
vector<int> pos[3];

int get(int x,int R,int p){
	if(R<0) return 0;
	if(pos[x][0]>p) return R+1;
	int l=0,r=R,t=0;
	while(l<=r){
		int m=(l+r)/2;
		if(pos[x][m]<=p) t=m,l=m+1; else r=m-1;
	}
	return R-t;
}

int main(){
	n=readint();
	scanf("%s",s);
	for(int i=0;i<n;i++){
		if(s[i]=='R') s[i]='A';
		if(s[i]=='Y') s[i]='B';
		if(s[i]=='G') s[i]='C';
		pos[s[i]-'A'].pb(i);
	}
	int ans=1e9,szA=pos[0].size(),szB=pos[1].size(),szC=pos[2].size();
	for(int i=0;i<=szA;i++)
		for(int j=0;j<=szB;j++)
			for(int k=0;k<=szC;k++)
				for(int p=0;p<3;p++)
					dp[i][j][k][p]=(i+j+k==0?0:1e9);
	for(int i=0;i<=szA;i++){
		for(int j=0;j<=szB;j++){
			for(int k=0;k<=szC;k++){
				for(int l=0;l<3;l++){
					if(i<szA&&l!=0){
						int p=pos[0][i]+get(0,i-1,pos[0][i])+get(1,j-1,pos[0][i])+get(2,k-1,pos[0][i]);
						chkmin(dp[i+1][j][k][0],dp[i][j][k][l]+p-i-j-k);
					}
					if(j<szB&&l!=1){
						int p=pos[1][j]+get(0,i-1,pos[1][j])+get(1,j-1,pos[1][j])+get(2,k-1,pos[1][j]);
						chkmin(dp[i][j+1][k][1],dp[i][j][k][l]+p-i-j-k);
					}
					if(k<szC&&l!=2){
						int p=pos[2][k]+get(0,i-1,pos[2][k])+get(1,j-1,pos[2][k])+get(2,k-1,pos[2][k]);
						chkmin(dp[i][j][k+1][2],dp[i][j][k][l]+p-i-j-k);
					}
				}
			}
		}
	}
	for(int i=0;i<3;i++)ans=min(ans,dp[szA][szB][szC][i]);
	printf("%d",(ans==1e9?-1:ans));
	return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 0 ms 340 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 4 ms 2388 KB Output is correct
19 Correct 3 ms 2388 KB Output is correct
20 Correct 3 ms 2516 KB Output is correct
21 Correct 3 ms 2004 KB Output is correct
22 Correct 3 ms 3028 KB Output is correct
23 Correct 3 ms 2004 KB Output is correct
24 Correct 2 ms 1492 KB Output is correct
25 Correct 1 ms 724 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 2 ms 1748 KB Output is correct
28 Correct 2 ms 2132 KB Output is correct
29 Correct 2 ms 2388 KB Output is correct
30 Correct 2 ms 1876 KB Output is correct
31 Correct 3 ms 1980 KB Output is correct
32 Correct 2 ms 1876 KB Output is correct
33 Correct 1 ms 724 KB Output is correct
34 Correct 1 ms 852 KB Output is correct
35 Correct 3 ms 1748 KB Output is correct
36 Correct 2 ms 2388 KB Output is correct
37 Correct 3 ms 1620 KB Output is correct
38 Correct 2 ms 1620 KB Output is correct
39 Correct 4 ms 2004 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 596 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 2260 KB Output is correct
3 Correct 4 ms 2332 KB Output is correct
4 Correct 6 ms 2332 KB Output is correct
5 Correct 7 ms 2260 KB Output is correct
6 Correct 5 ms 2260 KB Output is correct
7 Correct 6 ms 2260 KB Output is correct
8 Correct 6 ms 2260 KB Output is correct
9 Correct 6 ms 2320 KB Output is correct
10 Correct 6 ms 2260 KB Output is correct
11 Correct 8 ms 2340 KB Output is correct
12 Correct 2 ms 1236 KB Output is correct
13 Correct 3 ms 1492 KB Output is correct
14 Correct 4 ms 1876 KB Output is correct
15 Correct 6 ms 2260 KB Output is correct
16 Correct 5 ms 2324 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 4 ms 2388 KB Output is correct
19 Correct 3 ms 2388 KB Output is correct
20 Correct 3 ms 2516 KB Output is correct
21 Correct 3 ms 2004 KB Output is correct
22 Correct 3 ms 3028 KB Output is correct
23 Correct 3 ms 2004 KB Output is correct
24 Correct 2 ms 1492 KB Output is correct
25 Correct 1 ms 724 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 2 ms 1748 KB Output is correct
28 Correct 2 ms 2132 KB Output is correct
29 Correct 2 ms 2388 KB Output is correct
30 Correct 2 ms 1876 KB Output is correct
31 Correct 3 ms 1980 KB Output is correct
32 Correct 2 ms 1876 KB Output is correct
33 Correct 1 ms 724 KB Output is correct
34 Correct 1 ms 852 KB Output is correct
35 Correct 3 ms 1748 KB Output is correct
36 Correct 2 ms 2388 KB Output is correct
37 Correct 3 ms 1620 KB Output is correct
38 Correct 2 ms 1620 KB Output is correct
39 Correct 4 ms 2004 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 596 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 4 ms 2260 KB Output is correct
44 Correct 4 ms 2332 KB Output is correct
45 Correct 6 ms 2332 KB Output is correct
46 Correct 7 ms 2260 KB Output is correct
47 Correct 5 ms 2260 KB Output is correct
48 Correct 6 ms 2260 KB Output is correct
49 Correct 6 ms 2260 KB Output is correct
50 Correct 6 ms 2320 KB Output is correct
51 Correct 6 ms 2260 KB Output is correct
52 Correct 8 ms 2340 KB Output is correct
53 Correct 2 ms 1236 KB Output is correct
54 Correct 3 ms 1492 KB Output is correct
55 Correct 4 ms 1876 KB Output is correct
56 Correct 6 ms 2260 KB Output is correct
57 Correct 5 ms 2324 KB Output is correct
58 Execution timed out 511 ms 89700 KB Time limit exceeded
59 Halted 0 ms 0 KB -