oj.uz

Submission #252644

# Submission time Handle Problem Language Result Execution time Memory
252644 2020-07-26T03:08:20 Z yuma220284 Miners (IOI07_miners) C++14
100 / 100
 222 ms 101284 KB 
#include "bits/stdc++.h"
using namespace std;

int INF = 1000000000;

int main() {
	int N;
	string S;
	cin >> N >> S;
	vector<int> X(N);
	for (int i = 0; i < N; i++) {
		X[i] = S[i] % 3;
	}
	static int DP[100001][4][4][4][4] = {};
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				for (int l = 0; l < 4; l++) {
					for (int m = 0; m < 4; m++) {
						DP[i][j][k][l][m] = -INF;
					}
				}
			}
		}
	}
	DP[0][3][3][3][3] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				for (int l = 0; l < 4; l++) {
					for (int m = 0; m < 4; m++) {
						int A, B, C, D[3] = {};
						A = j, B = k, C = X[i], D[0] = D[1] = D[2] = 0;
						if (A == 3) A = X[i];
						if (B == 3) B = X[i];
						D[A] = D[B] = D[C] = 1;
						DP[i + 1][k][X[i]][l][m] = max(DP[i + 1][k][X[i]][l][m], DP[i][j][k][l][m] + D[0] + D[1] + D[2]);
						A = l, B = m, C = X[i], D[0] = D[1] = D[2] = 0;
						if (A == 3) A = X[i];
						if (B == 3) B = X[i];
						D[A] = D[B] = D[C] = 1;
						DP[i + 1][j][k][m][X[i]] = max(DP[i + 1][j][k][m][X[i]], DP[i][j][k][l][m] + D[0] + D[1] + D[2]);
					}
				}
			}
		}
	}
	int ANS = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				for (int l = 0; l < 4; l++) {
					ANS = max(ANS, DP[N][i][j][k][l]);
				}
			}
		}
	}
	cout << ANS << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1280 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5372 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10368 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 25604 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 76152 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 101284 KB Output is correct