Submission #701675

#	Time	Username	Problem	Language	Result	Execution time	Memory
701675		PenguinsAreCute	Lamps (JOI19_lamps)	C++17	100 / 100	82 ms	51456 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
int32_t main() {
    int N; cin >> N; string A, B; cin >> A >> B;
    int dp[N][3][2]; // idx, got 0 and got 1, got flip
    if(A[0] == B[0]) dp[0][0][0] = 0;
	else dp[0][0][0] = 1e15;
	if(B[0] == '0') dp[0][1][0] = 1;
	else dp[0][1][0] = 1e15;
	if(B[0] == '1') dp[0][2][0] = 1;
	else dp[0][2][0] = 1e15;
	if(A[0] != B[0]) dp[0][0][1] = 1;
	else dp[0][0][1] = 1e15;
	dp[0][1][1] = 2; dp[0][2][1] = 2;
    for(int i = 1; i < N; i++) {
		int minprev = 1e15;
		for(int j = 0; j < 3; j++) for(int k = 0; k < 2; k++) {
			minprev = min(minprev, dp[i - 1][j][k]);
		}
		if(A[i] == B[i]) dp[i][0][0] = minprev;
		else dp[i][0][0] = 1e15;
		if(B[i] == '0') dp[i][1][0] = min(minprev + 1, min(dp[i - 1][1][0], dp[i - 1][1][1]));
		else dp[i][1][0] = 1e15;
		if(B[i] == '1') dp[i][2][0] = min(minprev + 1, min(dp[i - 1][2][0], dp[i - 1][2][1]));
		else dp[i][2][0] = 1e15;
		if(A[i] != B[i]) dp[i][0][1] = min(minprev + 1, min(dp[i - 1][0][1], min(dp[i - 1][1][1], dp[i - 1][2][1])));
		else dp[i][0][1] = 1e15;
		dp[i][1][1] = min(minprev + 2, min(dp[i - 1][1][0], dp[i - 1][1][1]) + 1);
		dp[i][1][1] = min(dp[i][1][1], min(min(dp[i - 1][0][1], dp[i - 1][1][1]), dp[i - 1][2][1]) + 1);
		if(B[i] == B[i - 1]) {
			dp[i][1][1] = min(dp[i][1][1], dp[i - 1][1][1]);
		}
		dp[i][2][1] = min(minprev + 2, min(dp[i - 1][2][0], dp[i - 1][2][1]) + 1);
		dp[i][2][1] = min(dp[i][2][1], min(min(dp[i - 1][0][1], dp[i - 1][1][1]), dp[i - 1][2][1]) + 1);
		if(B[i] == B[i - 1]) {
			dp[i][2][1] = min(dp[i][2][1], dp[i - 1][2][1]);
		}
		// for(int k = 0; k < 3; k++) for(int j = 0; j < 2; j++) printf("%d %d %d %lld\n", i, k, j, dp[i][k][j]);
	}
	int ans = 1e15;
	for(int i = 0; i < 3; i++) for(int j = 0; j < 2; j++) ans = min(ans, dp[N - 1][i][j]);
	cout << ans;
}

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