Submission #435715

#	Time	Username	Problem	Language	Result	Execution time	Memory
435715		dutch	Lamps (JOI19_lamps)	C++17	100 / 100	49 ms	4472 KiB

lamp

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

const int INF = 1e18;

void r(int &a, int b){ a = min(a, b); }

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n; string a, b; cin >> n >> a >> b;
	array<int, 3> dp = {0, INF, INF}, c;

	for(int i=0; i<n; ++i){
		c = {INF, INF, INF};
		array<bool, 3> prev = {b[i-1] != a[i-1], b[i-1] == '1', b[i-1] == '0'};
		array<bool, 3> curr = {b[i] != a[i], b[i] == '1', b[i] == '0'};
		for(int j=0; j<3; ++j){
			for(int k=0; k<3; ++k){
				int cost = (k && k!=j) + (curr[k] && curr[k] != prev[j]);
				r(c[k], dp[j] + cost);
			}
		}
		swap(c, dp);
	}

	cout << min(dp[0], min(dp[1], dp[2]));
}

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