oj.uz

Submission #391614

# Submission time Handle Problem Language Result Execution time Memory
391614 2021-04-19T12:27:31 Z keta_tsimakuridze Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 5 ms 3348 KB 
#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=405,mod=1e16;
int t,dp[2][N][N][4],cnt[4],kth[4][N],aft[4][4][N][N],n;
string s;
 main(){
	// t=1;
	cin >> n;
	cin>>s;
	s='#'+s;
	for(int i=1;i<=n;i++){
		if(s[i]=='R') s[i]='0';
		else if(s[i]=='Y') s[i]='1';
		else s[i]='2';
		cnt[s[i]-'0']++;
		kth[s[i]-'0'][cnt[s[i]-'0']] = i;
	}
	for(int i=0;i<=2;i++){
		for(int j=0;j<=2;j++){
			if(i==j) continue;
			for(int k=0;k<=cnt[i];k++){
				for(int k1=1;k1<=cnt[j];k1++){
					aft[i][j][k][k1] = aft[i][j][k][k1-1] + (kth[j][k1] > kth[i][k]);
				}
			}
		}
	}
		for(int i=0;i<=n;i++){
		for(int j=0;j<=cnt[0];j++){
			for(int k=0;k<=cnt[1];k++){
				dp[0][j][k][0]=dp[0][j][k][1]=dp[0][j][k][2]=mod;
		}} }
	dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=cnt[0];j++){
			for(int k=0;k<=cnt[1];k++){
				if(i-k-j>cnt[2]) continue;
				dp[1][j][k][0]=dp[1][j][k][1]=dp[1][j][k][2]=mod;
				if(j) dp[1][j][k][0] = min(dp[0][j-1][k][1],dp[0][j-1][k][2]) + kth[0][j] + aft[0][1][j][k] + aft[0][2][j][i-k-j] - i;
				if(k) dp[1][j][k][1] = min(dp[0][j][k-1][2],dp[0][j][k-1][0]) + kth[1][k] + aft[1][0][k][j] + aft[1][2][k][i-k-j] - i;
				if(i-j-k) dp[1][j][k][2] = min(dp[0][j][k][1],dp[0][j][k][0]) + kth[2][i-j-k] + aft[2][0][i-j-k][j] + aft[2][1][i-j-k][k] - i;
			}
		}
		for(int j=0;j<=cnt[0];j++){
			for(int k=0;k<=cnt[1];k++){
				dp[0][j][k][0]=dp[1][j][k][0];
				dp[0][j][k][2]=dp[1][j][k][2];
				dp[0][j][k][1]=dp[1][j][k][1];
				
		}} 
	}
	int c = min(dp[0][cnt[0]][cnt[1]][0],min(dp[0][cnt[0]][cnt[1]][1],dp[0][cnt[0]][cnt[1]][2]));
	if(c==mod)cout<<-1;
	else cout<<c;
}

Compilation message

joi2019_ho_t3.cpp:9:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 |  main(){
      |       ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Incorrect 1 ms 460 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Incorrect 1 ms 460 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 3348 KB Output is correct
3 Correct 4 ms 3148 KB Output is correct
4 Correct 4 ms 3148 KB Output is correct
5 Correct 4 ms 3148 KB Output is correct
6 Correct 4 ms 3148 KB Output is correct
7 Correct 4 ms 3148 KB Output is correct
8 Correct 5 ms 3148 KB Output is correct
9 Correct 4 ms 3148 KB Output is correct
10 Correct 4 ms 3148 KB Output is correct
11 Correct 4 ms 3148 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 2252 KB Output is correct
14 Correct 3 ms 2636 KB Output is correct
15 Correct 4 ms 3200 KB Output is correct
16 Correct 4 ms 3148 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Incorrect 1 ms 460 KB Output isn't correct
14 Halted 0 ms 0 KB -