Submission #330655

#TimeUsernameProblemLanguageResultExecution timeMemory
330655limabeansLamps (JOI19_lamps)C++17
100 / 100
71 ms24124 KiB
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n;
int dp[maxn][5];


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    string a, b;
    cin>>a;
    cin>>b;

    for (int i=0; i<=n; i++) {
	for (int j=0; j<3; j++) {
	    dp[i][j] = n+10;
	}
    }

    //0: off
    //1: on
    //2: do nothing

    auto go = [&](int op, char c) {
	if (op==0) return '0';
	if (op==1) return '1';
	return c;
    };
    
    dp[0][2] = 0;
    for (int i=0; i<n; i++) {
	for (int p=0; p<3; p++) {
	    for (int j=0; j<3; j++) {
		int cur = dp[i][p];

		//new operation
		if (j!=p && j!=2) {
		    cur++;
		}

		//initiate flip
		if ((i==0 || go(p,a[i-1])==b[i-1]) && go(j,a[i])!=b[i]) {
		    cur++;
		}

		dp[i+1][j] = min(dp[i+1][j], cur);
	    }
	}
    }

    int res = n+10;
    for (int x=0; x<3; x++) {
	res = min(res, dp[n][x]);
    }
    cout<<res<<endl;    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...