제출 #204063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204063		ics0503	Lamps (JOI19_lamps)	C++17	10 / 100	283 ms	65016 KiB

lamp

#include<stdio.h>

char a[1212121], b[1212121];
int D[1212121][4][4];
int min(int a, int b) { if (a < b)return a; return b; }
bool oper(int type, int type2, int w) {
	if (type == 0)return b[w] == '0';
	if (type == 1)return b[w] == '1';
	if (type == 2 && type2 == 3)return b[w] != a[w];
	if (type == 2 && type2 == 2)return b[w] == a[w];
	if (type == 2 && type2 == 1)return b[w] == '0';
	if (type == 2 && type2 == 0)return b[w] == '1';
	if (type == 3 && type2 == 3)return a[w] == b[w];
	return oper(type2, 3, w);
}
int main() {
	int n, i, j, k, p, q; scanf("%d%s%s", &n, a + 1, b + 1);
	for (i = 0; i < 4; i++)for (j = 0; j < 4; j++)D[0][i][j] = 1e9;
	D[0][3][3] = 0;
	for (i = 1; i <= n; i++) {
		for (j = 0; j < 3; j++) {
			for (k = 0; k < 3; k++) {
				D[i][j][k] = 1e9;
				if (oper(j, k, i)) {
					D[i][j][k] = D[i - 1][j][k];
					for (p = 0; p < 4; p++) D[i][j][k] = min(D[i][j][k], D[i - 1][p][k] + (j != 3));
					D[i][j][k] = min(D[i][j][k], D[i - 1][k][3] + (j != 3));
				}
			}
			D[i][j][3] = 1e9;
			if (oper(j, 3, i)) {
				for (p = 0; p < 4; p++)D[i][j][3] = min(D[i][j][3], D[i - 1][j][p]);
				for (p = 0; p < 3; p++)D[i][j][3] = min(D[i][j][3], D[i - 1][p][j]);
				for (p = 0; p < 4; p++) {
					for (q = 0; q < 4; q++) {
						D[i][j][3] = min(D[i][j][3], D[i - 1][p][q] + 1);
					}
				}
			}
		}
		for (j = 0; j < 3; j++)D[i][3][j] = 1e9;
		D[i][3][3] = 1e9;
		for (j = 0; j < 4; j++) for (k = 0; k < 4; k++) {
			if (oper(3, 3, i)) D[i][3][3] = min(D[i][3][3], D[i - 1][j][k]);
		}
	}
	int ans = 1e9;
	for (i = 0; i < 4; i++)for (j = 0; j < 4; j++)ans = min(ans, D[n][i][j]);
	printf("%d", ans);

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

lamp.cpp: In function 'int main()':
lamp.cpp:17:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, i, j, k, p, q; scanf("%d%s%s", &n, a + 1, b + 1);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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