oj.uz

Submission #319653

# Submission time Handle Problem Language Result Execution time Memory
319653 2020-11-06T03:06:13 Z CodeTiger927 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 477 ms 1048580 KB 
using namespace std;

#include <iostream>
#include <cstring>

#define MAXN 405

long long dp[MAXN][MAXN][MAXN][3];
int N,prefix[MAXN][3],pos[MAXN][3],num[3];
string S;

inline int getNum(char c) {
	if(c == 'R') return 0;
	if(c == 'G') return 1;
	return 2;
}

int main() {
	cin >> N >> S;

	for(int i = 0;i < N;++i) {
		for(int j = 0;j < 3;++j) {
			prefix[i + 1][j] = prefix[i][j];
		}
		prefix[i + 1][getNum(S[i])]++;
		pos[++num[getNum(S[i])]][getNum(S[i])] = i + 1;
	}
	// 4557430888798830399
	memset(dp,63,sizeof(dp));
	for(int i = 0;i < 3;++i) {
		dp[0][0][0][i] = 0;
	}
	for(int i = 0;i <= num[0];++i) {
		for(int j = 0;j <= num[1];++j) {
			for(int k = 0;k <= num[2];++k) {
				for(int pre = 0;pre < 3;++pre) {
					for(int next = 0;next < 3;++next) {
						if(next == pre || (next == 0 && i == num[0]) || (next == 1 && j == num[1]) || (next == 2 && k == num[2])) continue;
						int posA,posB,posC,other;
						if(pre == 0) {
							posA = pos[i][0];
							if(next == 1) {
								posB = pos[j + 1][1];
								posC = pos[k][2];
								other = 2;
							}else{
								posB = pos[k + 1][2];
								posC = pos[j][1];
								other = 1;
							}
						}else if(pre == 1) {
							posA = pos[j][1];
							if(next == 0) {
								posB = pos[i + 1][0];
								posC = pos[k][2];
								other = 2;
							}else{
								posB = pos[k + 1][2];
								posC = pos[i][0];
								other = 0;
							}
						}else{
							posA = pos[k][2];
							if(next == 1) {
								posB = pos[j + 1][1];
								posC = pos[i][0];
								other = 0;
							}else{
								posB = pos[i + 1][0];
								posC = pos[j][1];
								other = 1;
							}
						}
						long long total = max(0,prefix[posB][pre] - prefix[posA][pre]) + max(0,prefix[posB][other] - prefix[posC][other]) + dp[i][j][k][pre];
						if(next == 0) {
							dp[i + 1][j][k][next] = min(dp[i + 1][j][k][next],total);
						}else if(next == 1) {
							dp[i][j + 1][k][next] = min(dp[i][j + 1][k][next],total);
						}else{
							dp[i][j][k + 1][next] = min(dp[i][j][k + 1][next],total);
						}
					}
				}
			}
		}
	}

	long long ans = 4557430888798830399;
	for(int i = 0;i < 3;++i) {
		ans = min(ans,dp[num[0]][num[1]][num[2]][i]);
	}
	cout << (ans == 4557430888798830399 ? -1 : ans) << endl;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 477 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 477 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 476 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 477 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -