제출 #1236094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236094		altern23	Lamps (JOI19_lamps)	C++20	4 / 100	533 ms	96340 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], 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])
*/

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