Submission #204719

#	Time	Username	Problem	Language	Result	Execution time	Memory
204719		achibasadzishvili	Lamps (JOI19_lamps)	C++17	100 / 100	218 ms	41608 KiB

lamp

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,a[1000003],b[1000003],dp[1000002][3];
int main(){
	cin >> n;
	
	for(int i=1; i<=n; i++){
		char x;
		cin >> x;
		a[i] = (x == '1');
	}
	
	for(int i=1; i<=n; i++){
		char x;
		cin >> x;
		b[i] = (x == '1');
	}
	
	dp[0][0] = dp[0][1] = 9999999999999;
	dp[0][2] = 0;
	
	for(int i=1; i<=n; i++){
		for(int j=0; j<3; j++){
			dp[i][j] = 10000000000000;
			for(int k=0; k<3; k++){
				ll cur = 0;
				if(j != 2 && j != k)cur++;
				ll ok = 0;
				if(k == 2 && a[i - 1] != b[i - 1])ok = 1;
				if(k != 2 && k != b[i - 1])ok = 1;
				ll es = a[i];
				if(j != 2)es = j;
				if(es != b[i])cur += (ok ^ 1);
				dp[i][j] = min(dp[i][j] , dp[i - 1][k] + cur);
			}
		}
	}
	
	cout << min(dp[n][0] , min(dp[n][1] , dp[n][2]));
	
	return 0;
}

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