Submission #1236119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236119		altern23	Lamps (JOI19_lamps)	C++20	4 / 100	23 ms	33776 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] && 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] + 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]));
				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])
*/

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