Submission #159663

#	Time	Username	Problem	Language	Result	Execution time	Memory
159663		Diuven	Lamps (JOI19_lamps)	C++14	100 / 100	32 ms	16120 KiB

lamp

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

const int MAX = 1e6+10;
inline int f(int a, int b){ return a<b ? a : b; }

int n, D[MAX][3]; // 0 1 x
char A[MAX], B[MAX];

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n>>(A+1)>>(B+1);
	D[1][0] = 1 + (B[1]!='0');
	D[1][1] = 1 + (B[1]!='1');
	D[1][2] = 0 + (B[1]!=A[1]);

	for(int i=2; i<=n; i++){
		int &z=D[i-1][0], &o=D[i-1][1], &x=D[i-1][2];
		int b=B[i]=='1';
		D[i][0] = f(z + (b && B[i-1]=='0'), x + 1 + (b && A[i-1]==B[i-1]));
		D[i][1] = f(o + (!b&& B[i-1]=='1'), x + 1 + (!b&& A[i-1]==B[i-1]));
		D[i][2] = f(f(
			z + (A[i]!=B[i] && B[i-1]=='0'),
			o + (A[i]!=B[i] && B[i-1]=='1')),
			x + (A[i]!=B[i] && A[i-1]==B[i-1]));
	}

	cout<<f(f(D[n][0], D[n][1]), D[n][2])<<'\n';

	return 0;
}

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