제출 #1159490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159490		KK_1729	Lamps (JOI19_lamps)	C++17	4 / 100	17 ms	26008 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
// #define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}


void solve(){
	int n; cin >> n;
	string a, b; cin >> a >> b;

	vector<int> A(n+5), B(n+5);
	FOR(i,1,n+1){
		if (a[i-1] == '0') A[i] = 0;
		else A[i] = 1;

		if (b[i-1] == '0') B[i] = 0;
		else B[i] = 1;
	}	


	int prev1 = 0; int prev2 = 0;
	int prev3 = 0;
	vector<int> dp(n+5, 1e9);
	dp[0] = 0;
	FOR(i,1,n+1){
		// if (i == 8) cout << prev1 << prev2 << endl;
		dp[i] = min(dp[i], dp[prev1]+1);
		if (A[i] == B[i]) prev1 = i;
		if (A[i] != B[i]) prev3 = i;
		int t = 0;
		if (prev3 > prev2) t = 1;
		dp[i] = min(dp[i], dp[prev2]+t);

		
		if (B[i] != B[i+1]) prev2 = i;
	}
	// printVector(dp);
	cout << dp[n] << endl;
}


int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int t = 1; // cin >> t;
	while (t--) solve();
}

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