Submission #102127

#	Time	Username	Problem	Language	Result	Execution time	Memory
102127		tpoppo	Lamps (JOI19_lamps)	C++14	4 / 100	68 ms	26060 KiB

lamp

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e6 + 100;
int n;
string a,b;

int dp[MAXN][2][3];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> n;
	cin >> a >> b;
	memset(dp,0x66,sizeof(dp));
	
	
	for(int inv=0;inv<2;inv++) {
		for(int z=0;z<3;z++) {
			dp[0][inv][z] = (inv == 1) + (z != 2);
		}
	}
	
	for(int i=0;i<=n;i++) {
		for(int inv=0;inv<2;inv++) {
			for(int z=0;z<3;z++) {

				//cout<<setw(10)<<dp[i][inv][z]<<" ";
				if(b[i] == '0') dp[i+1][inv][0] = min(dp[i+1][inv][0],dp[i][inv][z] + (z != 0) );
				if(b[i] == '0') dp[i+1][!inv][0] = min(dp[i+1][!inv][0],dp[i][inv][z] + (inv != 0) + (z != 0) );

				if(b[i] == '1') dp[i+1][inv][1] = min(dp[i+1][inv][1],dp[i][inv][z] + (z != 1) );
				if(b[i] == '1') dp[i+1][!inv][1] = min(dp[i+1][!inv][1],dp[i][inv][z]+ (inv != 0) + (z != 1) );

				if(b[i] == a[i]) dp[i+1][0][2] = min(dp[i+1][0][2],dp[i][inv][z]  );
				else dp[i+1][1][2] = min(dp[i+1][1][2],dp[i][inv][z] + (inv != 1) );
			}
		}//cout<<endl;
	}
	int rs = 1e9;
	for(int inv=0;inv<2;inv++) {
		for(int z=0;z<3;z++) {
			rs = min(rs,dp[n][inv][z]);
		}
	}

	cout<<rs<<'\n';

	return 0;
}

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