oj.uz

Submission #589812

# Submission time Handle Problem Language Result Execution time Memory
589812 2022-07-05T10:00:08 Z Zanite Miners (IOI07_miners) C++17
100 / 100
 167 ms 596 KB 
#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

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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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