oj.uz

답안 #886327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886327 2023-12-11T21:53:24 Z Hakiers Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 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 <= R; j++){
			for(int k = 0; k <= G; k++){
				//dla 0 -> {1, 2}
				//dla 1 -> {0, 2}
				//dla 2 -> {1, 2}
				
				//na pozycji itej stawiamy R
				if(j && (i - (j+k) >= 0))
					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 && (i - (j+k) >= 0))
					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) >= 0) && (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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 8 ms 43596 KB Output is correct
6 Correct 5 ms 45664 KB Output is correct
7 Correct 5 ms 47704 KB Output is correct
8 Correct 6 ms 45660 KB Output is correct
9 Correct 5 ms 45652 KB Output is correct
10 Incorrect 6 ms 53852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 8 ms 43596 KB Output is correct
6 Correct 5 ms 45664 KB Output is correct
7 Correct 5 ms 47704 KB Output is correct
8 Correct 6 ms 45660 KB Output is correct
9 Correct 5 ms 45652 KB Output is correct
10 Incorrect 6 ms 53852 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12636 KB Output is correct
2 Execution timed out 504 ms 1048580 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 5 ms 29020 KB Output is correct
5 Correct 8 ms 43596 KB Output is correct
6 Correct 5 ms 45664 KB Output is correct
7 Correct 5 ms 47704 KB Output is correct
8 Correct 6 ms 45660 KB Output is correct
9 Correct 5 ms 45652 KB Output is correct
10 Incorrect 6 ms 53852 KB Output isn't correct
11 Halted 0 ms 0 KB -