Submission #674039

#	Time	Username	Problem	Language	Result	Execution time	Memory
674039		rainboy	Lamps (JOI19_lamps)	C11	100 / 100	38 ms	4300 KiB

lamp

#include <stdio.h>
#include <string.h>

#define N	1000000
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int main() {
	static char aa[N + 1], bb[N + 1];
	static int dp[5], dq[5];
	int n, i, s, x, ans;

	scanf("%d%s%s", &n, aa, bb);
	for (i = 0; i < n; i++)
		aa[i] -= '0', bb[i] -= '0';
	memset(dp, 0x3f, sizeof dp), dp[4] = 0;
	for (i = 0; i < n; i++) {
		int a = i == 0 ? 0 : aa[i - 1], b = i == 0 ? 0 : bb[i - 1];

		memset(dq, 0x3f, sizeof dq);
		if ((x = dp[0]) != INF) {
			dq[0] = min(dq[0], x + (b == 0 && bb[i] != 0 ? 1 : 0));
			dq[3] = min(dq[3], x + (b == 0 && bb[i] != 1 ? 1 : 0) + 1);
			dq[4] = min(dq[4], x + (b == 0 && bb[i] != aa[i] ? 1 : 0));
		}
		if ((x = dp[1]) != INF) {
			dq[1] = min(dq[1], x + (b == 0 && bb[i] != 0 ? 1 : 0));
			dq[2] = min(dq[2], x + (b == 0 && bb[i] != 1 ? 1 : 0));
			dq[4] = min(dq[4], x + (b == 0 && bb[i] != aa[i] ? 1 : 0));
		}
		if ((x = dp[2]) != INF) {
			dq[1] = min(dq[1], x + (b == 1 && bb[i] != 0 ? 1 : 0) + 1);
			dq[2] = min(dq[2], x + (b == 1 && bb[i] != 1 ? 1 : 0));
			dq[4] = min(dq[4], x + (b == 1 && bb[i] != aa[i] ? 1 : 0));
		}
		if ((x = dp[3]) != INF) {
			dq[0] = min(dq[0], x + (b == 1 && bb[i] != 0 ? 1 : 0));
			dq[3] = min(dq[3], x + (b == 1 && bb[i] != 1 ? 1 : 0));
			dq[4] = min(dq[4], x + (b == 1 && bb[i] != aa[i] ? 1 : 0));
		}
		if ((x = dp[4]) != INF) {
			dq[0] = min(dq[0], x + (b == a && bb[i] != 0 ? 1 : 0) + 1);
			dq[2] = min(dq[2], x + (b == a && bb[i] != 1 ? 1 : 0) + 1);
			dq[4] = min(dq[4], x + (b == a && bb[i] != aa[i] ? 1 : 0));
		}
		memcpy(dp, dq, sizeof dq);
	}
	ans = INF;
	for (s = 0; s < 5; s++)
		ans = min(ans, dp[s]);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49