oj.uz

Submission #886338

# Submission time Handle Problem Language Result Execution time Memory
886338 2023-12-11T22:21:57 Z Hakiers Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
5 / 100
 476 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 407;
constexpr int oo = 1e9;
int sumpref[MAXN][3];
int POS[MAXN][MAXN][MAXN][3];
int dp[MAXN][MAXN][MAXN][3];
vector<int> idx[3];
int R,G,Y;
int n;

int check(int i, int j, int k, int v){
	int ith, sum = 0;
	if(v == 0)
		ith = idx[v][i-1];
	if(v == 1)
		ith = idx[v][j-1];
	if(v == 2)
		ith = idx[v][k-1];
	
	sum += max(sumpref[ith][0], i);
	sum += max(sumpref[ith][1], j);
	sum += max(sumpref[ith][2], k);
	
	return sum;
}

void computePos(){
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			for(int k = 1; k <= n; k++){
				if(k <= R && i <= G && j <= Y)
					POS[k][i][j][0] = check(k, i, j, 0);
				if(i <= R && k <= G && j <= Y)
					POS[i][k][j][1] = check(i, k, j, 1);
				if(i <= R && j <= G && k <= Y)
					POS[i][j][k][2] = check(i, j, k, 2);
			}
		}
	}
}

void solve(){
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k <= n; k++)
				dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = oo;
				
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	
	
	//dp[i][j][k][v]
	// i -> pozycja
	// j -> ile R
	// k -> ile G
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= min(R, i); j++){
			for(int k = 0; k <= min(G, i); k++){
				//dla 0 -> {1, 2}
				//dla 1 -> {0, 2}
				//dla 2 -> {1, 2}
				
				//na pozycji itej stawiamy R
				if(j && j+k <= i)
					dp[i][j][k][0] = min(dp[i-1][j-1][k][1], dp[i-1][j-1][k][2]) + abs(i - POS[j][k][i - (j+k)][0]);
				
				//na pozycji itej stawiamy G
				if(k && j+k <= i)
					dp[i][j][k][1] = min(dp[i-1][j][k-1][0], dp[i-1][j][k-1][2]) + abs(i - POS[j][k][i - (j+k)][1]);
				
				//na pozycji itej stawiamy Y
				if(i >= j+k && (i - (j+k) <= Y))
					dp[i][j][k][2] = min(dp[i-1][j][k][0], dp[i-1][j][k][1]) + abs(i - POS[j][k][i - (j+k)][2]);
			
			}
		}
	}

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		char c;
		cin >> c;
		if(c == 'R'){
			idx[0].push_back(i);
			R++;
		}
		else if(c == 'G'){
			idx[1].push_back(i);
			G++;
		}
		else if(c == 'Y'){
			idx[2].push_back(i);
			Y++;
		}
	
		sumpref[i][0] = R;
		sumpref[i][1] = G;
		sumpref[i][2] = Y;
	}

	computePos();
	solve();
	
	int res = min({dp[n][R][G][0], dp[n][R][G][1], dp[n][R][G][2]});
	if(res > 2*n) cout << "-1 \n";
	else cout << res << "\n";
	
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 3 ms 29016 KB Output is correct
5 Correct 7 ms 43484 KB Output is correct
6 Correct 5 ms 45664 KB Output is correct
7 Correct 6 ms 47704 KB Output is correct
8 Correct 6 ms 45656 KB Output is correct
9 Correct 5 ms 45656 KB Output is correct
10 Correct 6 ms 53852 KB Output is correct
11 Correct 5 ms 43476 KB Output is correct
12 Correct 5 ms 43612 KB Output is correct
13 Correct 4 ms 39516 KB Output is correct
14 Correct 5 ms 43584 KB Output is correct
15 Correct 4 ms 41544 KB Output is correct
16 Correct 7 ms 55900 KB Output is correct
17 Correct 4 ms 31188 KB Output is correct

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 3 ms 29016 KB Output is correct
5 Correct 7 ms 43484 KB Output is correct
6 Correct 5 ms 45664 KB Output is correct
7 Correct 6 ms 47704 KB Output is correct
8 Correct 6 ms 45656 KB Output is correct
9 Correct 5 ms 45656 KB Output is correct
10 Correct 6 ms 53852 KB Output is correct
11 Correct 5 ms 43476 KB Output is correct
12 Correct 5 ms 43612 KB Output is correct
13 Correct 4 ms 39516 KB Output is correct
14 Correct 5 ms 43584 KB Output is correct
15 Correct 4 ms 41544 KB Output is correct
16 Correct 7 ms 55900 KB Output is correct
17 Correct 4 ms 31188 KB Output is correct
18 Correct 23 ms 164700 KB Output is correct
19 Correct 17 ms 156508 KB Output is correct
20 Correct 23 ms 168900 KB Output is correct
21 Correct 19 ms 158504 KB Output is correct
22 Correct 19 ms 166748 KB Output is correct
23 Correct 16 ms 152412 KB Output is correct
24 Correct 15 ms 140264 KB Output is correct
25 Correct 20 ms 191444 KB Output is correct
26 Correct 20 ms 180996 KB Output is correct
27 Incorrect 20 ms 172816 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12756 KB Output is correct
2 Runtime error 476 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 3 ms 29016 KB Output is correct
5 Correct 7 ms 43484 KB Output is correct
6 Correct 5 ms 45664 KB Output is correct
7 Correct 6 ms 47704 KB Output is correct
8 Correct 6 ms 45656 KB Output is correct
9 Correct 5 ms 45656 KB Output is correct
10 Correct 6 ms 53852 KB Output is correct
11 Correct 5 ms 43476 KB Output is correct
12 Correct 5 ms 43612 KB Output is correct
13 Correct 4 ms 39516 KB Output is correct
14 Correct 5 ms 43584 KB Output is correct
15 Correct 4 ms 41544 KB Output is correct
16 Correct 7 ms 55900 KB Output is correct
17 Correct 4 ms 31188 KB Output is correct
18 Correct 23 ms 164700 KB Output is correct
19 Correct 17 ms 156508 KB Output is correct
20 Correct 23 ms 168900 KB Output is correct
21 Correct 19 ms 158504 KB Output is correct
22 Correct 19 ms 166748 KB Output is correct
23 Correct 16 ms 152412 KB Output is correct
24 Correct 15 ms 140264 KB Output is correct
25 Correct 20 ms 191444 KB Output is correct
26 Correct 20 ms 180996 KB Output is correct
27 Incorrect 20 ms 172816 KB Output isn't correct
28 Halted 0 ms 0 KB -