Submission #1001353

#TimeUsernameProblemLanguageResultExecution timeMemory
1001353biximoLamps (JOI19_lamps)C++17
10 / 100
37 ms35772 KiB
#include <bits/stdc++.h>
#define N 1000005
#define INF 1000000000
using namespace std;
void chmin(int& a, int v) {
	a = min(a,v);
}
/* 
0 - none
1 - flip
2 - ons
3 - offs
4 - flip, ons
5 - flip, offs
6 - ons, flip
7 - offs, flip  
*/
int n, dp[N][8];
string A, B;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> A >> B;
    for(auto&i: dp) for(auto&j: i) j = INF;
    dp[0][0] = 0;
	for(int i = 0; i < n; i ++) {
		if(A[i] == B[i]) {
			chmin(dp[i+1][0],min({dp[i][0],dp[i][1],dp[i][2],dp[i][3],dp[i][4],dp[i][5],dp[i][6],dp[i][7]}));
		} else {
			chmin(dp[i+1][1],min({dp[i][0]+1,dp[i][1],dp[i][4],dp[i][5],dp[i][6],dp[i][7]}));
		}

		if(B[i] == '1') {
			chmin(dp[i+1][2],min({dp[i][0]+1,dp[i][2],dp[i][4],dp[i][6]}));
			chmin(dp[i+1][6],min({dp[i][6],dp[i][1]+1}));
			chmin(dp[i+1][5],min({dp[i][5],dp[i][3]+1}));

		} else {
			chmin(dp[i+1][3],min({dp[i][0]+1,dp[i][3],dp[i][5],dp[i][7]}));
			chmin(dp[i+1][4],min({dp[i][4],dp[i][2]+1}));
			chmin(dp[i+1][7],min({dp[i][7],dp[i][1]+1}));
		}
	}
	int ans = INF;
	for(int i = 0; i < 8; i ++) {
		ans = min(ans, dp[n][i]);
	}
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...