Submission #330655

#	Time	Username	Problem	Language	Result	Execution time	Memory
330655		limabeans	Lamps (JOI19_lamps)	C++17	100 / 100	71 ms	24124 KiB

lamp

#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;
}

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