oj.uz

Submission #391577

# Submission time Handle Problem Language Result Execution time Memory
391577 2021-04-19T12:03:38 Z keta_tsimakuridze Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 141 ms 328268 KB 
#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=405,mod=1e9+7;
int t,dp[N][N][N][3],cnt[3],kth[3][N],aft[3][3][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=1;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[i][j][k][0]=dp[i][j][k][1]=dp[i][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;
				if(j) dp[i][j][k][0] = min(dp[i-1][j-1][k][1],dp[i-1][j-1][k][2]) + kth[0][j] + aft[0][1][j][k] + aft[0][2][j][i-k-j] - i;
				if(k) dp[i][j][k][1] = min(dp[i-1][j][k-1][2],dp[i-1][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[i][j][k][2] = min(dp[i-1][j][k][1],dp[i-1][j][k][0]) + kth[2][i-j-k] + aft[2][0][i-j-k][j] + aft[2][1][i-j-k][k] - i;
			}
		}
	}
	int c = min(dp[n][cnt[0]][cnt[1]][0],min(dp[n][cnt[0]][cnt[1]][1],dp[n][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 588 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Incorrect 1 ms 716 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 588 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Incorrect 1 ms 716 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 141 ms 328264 KB Output is correct
3 Correct 131 ms 327364 KB Output is correct
4 Correct 128 ms 328188 KB Output is correct
5 Correct 130 ms 328216 KB Output is correct
6 Correct 129 ms 328200 KB Output is correct
7 Correct 129 ms 325840 KB Output is correct
8 Correct 126 ms 325780 KB Output is correct
9 Correct 131 ms 324960 KB Output is correct
10 Correct 128 ms 328240 KB Output is correct
11 Correct 127 ms 328268 KB Output is correct
12 Correct 35 ms 88516 KB Output is correct
13 Correct 61 ms 155280 KB Output is correct
14 Correct 88 ms 224252 KB Output is correct
15 Correct 126 ms 326548 KB Output is correct
16 Correct 127 ms 326596 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 588 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 844 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Incorrect 1 ms 716 KB Output isn't correct
14 Halted 0 ms 0 KB -