Submission #596773

#	Time	Username	Problem	Language	Result	Execution time	Memory
596773		penguinhacker	Lamps (JOI19_lamps)	C++17	100 / 100	54 ms	23720 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e6;
int n, dp[mxN][5]; // use nothing, use 0 parity 1, use 0 parity 0, use 1 parity 1, use 1 parity 0
string a, b;

bool ck(int i, int t) {
	char x=t==0?a[i]:t<=2?'0':'1';
	return x!=b[i];
}

bool bad(int i, int j, int k) {
	return ck(i, j)&&!ck(i-1, k);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> a >> b;
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0]=(a[0]!=b[0]);
	dp[0][1]=1+(b[0]=='1');
	dp[0][3]=1+(b[0]=='0');
	for (int i=1; i<n; ++i) {
		dp[i][0]=min(dp[i][0], dp[i-1][0]+bad(i, 0, 0));
		dp[i][1]=min(dp[i][1], dp[i-1][0]+bad(i, 1, 0)+1);
		dp[i][3]=min(dp[i][3], dp[i-1][0]+bad(i, 3, 0)+1);
		for (int j=1; j<5; ++j) {
			dp[i][j]=min(dp[i][j], dp[i-1][j]+bad(i, j, j));
			dp[i][0]=min(dp[i][0], dp[i-1][j]+bad(i, 0, j));
			dp[i][5-j]=min(dp[i][5-j], dp[i-1][j]+bad(i, 5-j, j)+(j%2));
		}
	}
	cout << *min_element(dp[n-1], dp[n-1]+5);
	return 0;
}

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