Submission #1114193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114193		yellowtoad	Lamps (JOI19_lamps)	C++17	4 / 100	38 ms	21060 KiB

lamp

#include <iostream>
using namespace std;

int n, dp[1000010][4];
string s, t;

int main() {
	cin >> n >> s >> t;
	for (int i = 0; i <= n; i++) for (int j = 0; j < 4; j++) dp[i][j] = 1e9;
	dp[0][0] = 0;
	s = " "+s; t = " "+t;
	for (int i = 1; i <= n; i++) {
		if (s[i] == t[i]) dp[i][0] = min(min(dp[i-1][0],dp[i-1][1]),min(dp[i-1][2],dp[i-1][3]));
		if (t[i] == '0') dp[i][1] = min(min(dp[i-1][0]+1,dp[i-1][1]),min(dp[i-1][2]+1,dp[i-1][3]+1));
		if (t[i] == '1') dp[i][2] = min(min(dp[i-1][0]+1,dp[i-1][1]+1),min(dp[i-1][2],dp[i-1][3]+1));
		if (s[i] != t[i]) dp[i][3] = min(min(dp[i-1][0]+1,dp[i-1][1]+1),min(dp[i-1][2]+1,dp[i-1][3]));
	}
	cout << min(min(dp[n][0],dp[n][1]),min(dp[n][2],dp[n][3])) << endl;
}

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