제출 #1236303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236303		altern23	Lamps (JOI19_lamps)	C++20	100 / 100	87 ms	127776 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e6;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

ll dp[MAXN + 5][4][4];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		string A, B; cin >> A >> B;
		A = '%' + A, B = '$' + B;
		
		for(int i = 0; i <= N; i++){
			for(int j = 0; j < 3; j++){
				for(int k = 0; k < 2; k++) dp[i][j][k] = INF;
			}
		}
		
		dp[0][0][0] = 0;
		for(int i = 1; i <= N; i++){
			for(int j = 0; j < 3; j++){
				for(int k = 0; k < 2; k++){
					if(B[i] == '1'){
						dp[i][1][0] = min(dp[i][1][0], dp[i - 1][j][k] + (j != 1));
						dp[i][2][1] = min(dp[i][2][1], dp[i - 1][j][k] + (j != 2) + (k != 1));
					}
					if(B[i] == '0'){
						dp[i][1][1] = min(dp[i][1][1], dp[i - 1][j][k] + (j != 1) + (k != 1));
						dp[i][2][0] = min(dp[i][2][0], dp[i - 1][j][k] + (j != 2));
					}
					if(A[i] == B[i]){
						dp[i][0][0] = min(dp[i][0][0], dp[i - 1][j][k]);
					}
					if(A[i] != B[i]){
						dp[i][0][1] = min(dp[i][0][1], dp[i - 1][j][k] + (k != 1));
					}
				}
			}
		}
		
		ll ans = INF;
		for(int i = 0; i < 3; i++){
			for(int j = 0; j < 2; j++) ans = min(ans, dp[N][i][j]);
		}
		
		cout << ans << "\n";
	}	
}

/*
dp[j] + 1 + (ps[i] - ps[j])
*/

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