Submission #755154

#	Time	Username	Problem	Language	Result	Execution time	Memory
755154		Dan4Life	Lamps (JOI19_lamps)	C++17	47 / 100	9 ms	7884 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define all(a) begin(a),end(a)

const int mxN = (int)2e5+10;

string s, ss;
int n, a[mxN], b[mxN], dp[mxN][3];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> s >> ss; int ans = mxN;
	for(int i = 0; i < n; i++) 
		a[i+1] = s[i]=='1', b[i+1] = ss[i]=='1';
	memset(dp,63,sizeof(dp)); dp[0][2] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 3; j++){
			bool eq = ((j==2 and a[i]==b[i]) or j==b[i]);
			dp[i][j] = min(dp[i][j], dp[i-1][0]+!b[i-1]*!eq+(j==1));
			dp[i][j] = min(dp[i][j], dp[i-1][1]+b[i-1]*!eq+(j==0));
			dp[i][j] = min(dp[i][j], dp[i-1][2]+!eq*(a[i-1]==b[i-1])+(j!=2));
			if(i==n) ans = min(ans, dp[i][j]);
		}
	}
	cout << ans;
}

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