Submission #1001364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001364		biximo	Lamps (JOI19_lamps)	C++17	10 / 100	37 ms	35760 KiB

lamp

#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][2]+1,dp[i][3]+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][1]+1,dp[i][2],dp[i][3]+1,dp[i][4],dp[i][5]+1,dp[i][6],dp[i][7]+1}));
			chmin(dp[i+1][6],min({dp[i][0]+2,dp[i][1]+1,dp[i][2]+2,dp[i][3]+2,dp[i][4]+1,dp[i][5]+1,dp[i][6],dp[i][7]+1}));
			chmin(dp[i+1][5],min({dp[i][0]+2,dp[i][1]+2,dp[i][2]+2,dp[i][3]+1,dp[i][4]+2,dp[i][5],dp[i][6]+2,dp[i][7]+1}));

		} else {
			chmin(dp[i+1][3],min({dp[i][0]+1,dp[i][1]+1,dp[i][2]+1,dp[i][3],dp[i][4]+1,dp[i][5],dp[i][6]+1,dp[i][7]}));
			chmin(dp[i+1][4],min({dp[i][0]+2,dp[i][1]+2,dp[i][2]+1,dp[i][3]+2,dp[i][4],dp[i][5]+2,dp[i][6]+1,dp[i][7]+2}));
			chmin(dp[i+1][7],min({dp[i][0]+2,dp[i][1]+1,dp[i][2]+2,dp[i][3]+2,dp[i][4]+1,dp[i][5]+1,dp[i][6]+1,dp[i][7]}));
		}
	}
	int ans = INF;
	for(int i = 0; i < 8; i ++) {
		ans = min(ans, dp[n][i]);
	}
	cout << ans;
}

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