Submission #447994

#	Time	Username	Problem	Language	Result	Execution time	Memory
447994		rainboy	Miners (IOI07_miners)	C11	100 / 100	129 ms	580 KiB

miners

#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 (stderr)

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 / 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