Submission #1236095

#TimeUsernameProblemLanguageResultExecution timeMemory
1236095altern23Lamps (JOI19_lamps)C++20
4 / 100
27 ms33776 KiB
#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], ps[MAXN + 5][3];

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 = 1; i <= N; i++){
			dp[i] = INF;
			ps[i][0] += ps[i - 1][0] + (B[i] == '0' && B[i - 1] != '0');
			ps[i][1] += ps[i - 1][1] + (B[i] == '1' && B[i - 1] != '1');
			ps[i][2] += ps[i - 1][2] + (A[i] != B[i] && A[i - 1] == B[i - 1]);
		}
		
		map<ll, ll> mp;
		mp[0] = 0;
		
		vector<ll> MN(3);
		dp[0] = 0;
		for(int i = 1; i <= N; i++){
			if(A[i] == B[i]) dp[i] = dp[i - 1];
			dp[i] = min(dp[i], MN[0] + ps[i][0] + 1);
			dp[i] = min(dp[i], MN[1] + ps[i][1] + 1);
			dp[i] = min(dp[i], MN[2] + ps[i][2]);
			
			if(i < N){
				MN[0] = min(MN[0], dp[i] - ps[i][0] + (B[i + 1] == '0' && B[i + 1] == B[i]));
				MN[1] = min(MN[1], dp[i] - ps[i][1] + (B[i + 1] == '1' && B[i + 1] == B[i]));
				MN[2] = min(MN[2], dp[i] - ps[i][2] + (B[i + 1] != A[i + 1] && B[i] != A[i]));
			}			
		}
		
		cout << dp[N] << "\n";
	}	
}

/*
dp[j] + 1 + (ps[i] - ps[j])
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...