oj.uz

Submission #447994

# Submission time Handle Problem Language Result Execution time Memory
447994 2021-07-28T12:16:48 Z rainboy Miners (IOI07_miners) C
100 / 100
 129 ms 580 KB 
#include <stdio.h>
#include <string.h>

#define N	100000

int max(int a, int b) { return a > b ? a : b; }

char used[4];

int count(int a, int b, int c) {
	int k;

	memset(used, 0, sizeof used);
	k = 0;
	if (a > 0 && !used[a])
		used[a] = 1, k++;
	if (b > 0 && !used[b])
		used[b] = 1, k++;
	if (c > 0 && !used[c])
		used[c] = 1, k++;
	return k;
}

int main() {
	static char cc[N + 1];
	static int dp[4][4][4][4], dq[4][4][4][4];
	int n, i, a, b, c, d, ans;

	scanf("%d%s", &n, cc);
	memset(dp, -1, sizeof dp);
	dp[0][0][0][0] = 0;
	for (i = 0; i < n; i++) {
		int e = cc[i] == 'M' ? 1 : (cc[i] == 'F' ? 2 : 3);

		memset(dq, -1, sizeof dq);
		for (a = 0; a < 4; a++)
			for (b = 0; b < 4; b++)
				for (c = 0; c < 4; c++)
					for (d = 0; d < 4; d++) {
						int x = dp[a][b][c][d];

						if (x == -1)
							continue;
						dq[b][e][c][d] = max(dq[b][e][c][d], x + count(a, b, e));
						dq[a][b][d][e] = max(dq[a][b][d][e], x + count(c, d, e));
					}
		for (a = 0; a < 4; a++)
			for (b = 0; b < 4; b++)
				for (c = 0; c < 4; c++)
					for (d = 0; d < 4; d++)
						dp[a][b][c][d] = dq[a][b][c][d];
	}
	ans = 0;
	for (a = 0; a < 4; a++)
		for (b = 0; b < 4; b++)
			for (c = 0; c < 4; c++)
				for (d = 0; d < 4; d++)
					ans = max(ans, dp[a][b][c][d]);
	printf("%d\n", ans);
	return 0;
}

Compilation message

miners.c: In function 'main':
miners.c:29:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d%s", &n, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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