Submission #589812

#	Time	Username	Problem	Language	Result	Execution time	Memory
589812		Zanite	Miners (IOI07_miners)	C++17	100 / 100	167 ms	596 KiB

miners

#include <bits/stdc++.h>
using namespace std;

const int maxN	= 1e5 + 5;
const int INF	= 2e9;

int N;
int shipments[maxN];
int dp[2][4][4][4][4];

inline void chmax(int &a, int b) {a = max(a, b);}

void resetDP(int 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;
				}
			}
		}
	}
}

int main() {
	scanf("%d", &N);
	char _tmp;
	for (int i = 1; i <= N; i++) {
		scanf(" %c", &_tmp);
		if (_tmp == 'M') {shipments[i] = 1;}
		else if (_tmp == 'B') {shipments[i] = 2;}
		else {shipments[i] = 3;}
	}

	resetDP(0);
	dp[0][0][0][0][0] = 0;

	for (int i = 0; i < N; i++) {
		int cur = i & 1, nxt = cur ^ 1;
		resetDP(nxt);

		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[4] = {}, B[4] = {};
						A[j]++, A[k]++, B[l]++, B[m]++;
						A[shipments[i+1]]++, B[shipments[i+1]]++;

						int X = 0, Y = 0;
						for (int i = 1; i <= 3; i++) {
							if (A[i]) X++;
							if (B[i]) Y++;
						}

						int D = dp[cur][j][k][l][m];

						chmax(dp[nxt][k][shipments[i+1]][l][m], D + X);
						chmax(dp[nxt][j][k][m][shipments[i+1]], D + Y);
					}
				}
			}
		}
	}

	int ans = -INF;
	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++) {
					chmax(ans, dp[N & 1][j][k][l][m]);
				}
			}
		}
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
miners.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf(" %c", &_tmp);
      |   ~~~~~^~~~~~~~~~~~~~

• 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