Submission #701970

#	Time	Username	Problem	Language	Result	Execution time	Memory
701970		PenguinsAreCute	Lamps (JOI19_lamps)	C++17	100 / 100	98 ms	51468 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][6];
    if(A[0] == B[0]) dp[0][0] = 0;
	else dp[0][0] = 1e15;
	if(B[0] == '0') dp[0][1] = 1;
	else dp[0][1] = 1e15;
	if(B[0] == '1') dp[0][2] = 1;
	else dp[0][2] = 1e15;
	if(A[0] != B[0]) dp[0][3] = 1;
	else dp[0][3] = 1e15;
	dp[0][4] = 2; dp[0][5] = 2;
    for(int i = 1; i < N; i++) {
		int minprev = 1e15, minFlip, min0, min1;
		for(int j = 0; j < 6; j++) minprev = min(minprev, dp[i - 1][j]);
		min0 = min(dp[i - 1][1], dp[i - 1][4]);
		min1 = min(dp[i - 1][2], dp[i - 1][5]);
		minFlip = min(dp[i - 1][3], min(dp[i - 1][4], dp[i - 1][5]));
		if(A[i] == B[i]) dp[i][0] = minprev;
		else dp[i][0] = 1e15;
		if(B[i] == '0') dp[i][1] = min(minprev + 1, min0);
		else dp[i][1] = 1e15;
		if(B[i] == '1') dp[i][2] = min(minprev + 1, min1);
		else dp[i][2] = 1e15;
		if(A[i] != B[i]) dp[i][3] = min(minprev + 1, minFlip);
		else dp[i][3] = 1e15;
		dp[i][4] = min(minprev + 2, min0 + 1);
		dp[i][4] = min(dp[i][4], minFlip + 1);
		if(B[i] == B[i - 1]) {
			dp[i][4] = min(dp[i][4], dp[i - 1][4]);
		}
		dp[i][5] = min(minprev + 2, min1 + 1);
		dp[i][5] = min(dp[i][5], minFlip + 1);
		if(B[i] == B[i - 1]) {
			dp[i][5] = min(dp[i][5], dp[i - 1][5]);
		}
	}
	int ans = 1e15;
	for(int i = 0; i < 6; i++) ans = min(ans, dp[N - 1][i]);
	cout << ans;
}

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