Submission #105076

#	Time	Username	Problem	Language	Result	Execution time	Memory
105076		Just_Solve_The_Problem	Lamps (JOI19_lamps)	C++11	100 / 100	187 ms	28344 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e6 + 7;

string a, b;
int n;
int dp[N][3][2];
/*
dp[pos][operation][xor]
operation
0 = off
1 = on
2 = do not touch
*/

main() {
	memset(dp, 63, sizeof dp);
	scanf("%d", &n);
	cin >> a >> b;
	a = " " + a;
	b = " " + b;
	dp[0][2][0] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			if (b[i] - '0' == j) {
				dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0]);
				dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][1]);
				for (int l = 0; l < 3; l++) {
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][l][0] + 1);
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][l][1] + 1);
				}
			}
			if (b[i] - '0' == (j ^ 1)) {
				dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1]);
				dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][0] + 1);
				for (int l = 0; l < 3; l++) {
					dp[i][j][1] = min(dp[i][j][1], dp[i - 1][l][1] + 1);
				}
			}
			if (j == 2 && b[i] == a[i]) {
				for (int l = 0; l < 3; l++) {
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][l][0]);
					dp[i][j][0] = min(dp[i][j][0], dp[i - 1][l][1]);
				}
			}
			if (j == 2 && b[i] != a[i]) {
				for (int l = 0; l < 3; l++) {
					dp[i][j][1] = min(dp[i][j][1], dp[i - 1][l][0] + 1);
					dp[i][j][1] = min(dp[i][j][1], dp[i - 1][l][1]);
				}
			}
		}
	}
	int ans = dp[0][1][0];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 2; j++) {
			ans = min(ans, dp[n][i][j]);
		}
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

lamp.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
lamp.cpp: In function 'int main()':
lamp.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~

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