Submission #1236094

#TimeUsernameProblemLanguageResultExecution timeMemory
1236094altern23Lamps (JOI19_lamps)C++20
4 / 100
533 ms96340 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]);
		}
		
		map<ll, ll> mp;
		mp[0] = 0;
		
		vector<ll> MN(2);
		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);
			if(mp.count(ps[i][2] - i)) dp[i] = min(dp[i], mp[ps[i][2] - i] + 1);
			
			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]));
				if(!mp.count(ps[i][2] - i)) mp[ps[i][2] - i] = dp[i];
				else mp[ps[i][2] - i] = min(mp[ps[i][2] - i], dp[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...