oj.uz

Submission #886331

# Submission time Handle Problem Language Result Execution time Memory
886331 2023-12-11T22:09:59 Z Hakiers Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 472 ms 1048580 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 == oo) cout << "-1 \n";
	else cout << res << "\n";
	
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 6 ms 43404 KB Output is correct
6 Correct 6 ms 45660 KB Output is correct
7 Correct 6 ms 47708 KB Output is correct
8 Correct 5 ms 45660 KB Output is correct
9 Correct 5 ms 45660 KB Output is correct
10 Incorrect 7 ms 53852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 6 ms 43404 KB Output is correct
6 Correct 6 ms 45660 KB Output is correct
7 Correct 6 ms 47708 KB Output is correct
8 Correct 5 ms 45660 KB Output is correct
9 Correct 5 ms 45660 KB Output is correct
10 Incorrect 7 ms 53852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Runtime error 472 ms 1048580 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 4440 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 6 ms 43404 KB Output is correct
6 Correct 6 ms 45660 KB Output is correct
7 Correct 6 ms 47708 KB Output is correct
8 Correct 5 ms 45660 KB Output is correct
9 Correct 5 ms 45660 KB Output is correct
10 Incorrect 7 ms 53852 KB Output isn't correct
11 Halted 0 ms 0 KB -