Submission #252644

#	Time	Username	Problem	Language	Result	Execution time	Memory
252644		yuma220284	Miners (IOI07_miners)	C++14	100 / 100	222 ms	101284 KiB

miners

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8