제출 #1306367

#제출 시각아이디문제언어결과실행 시간메모리
1306367vlomaczkLamps (JOI19_lamps)C++20
100 / 100
81 ms65148 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int g(int x, int k) {
	if(k==0) return 0;
	if(k==1) return 1;
	if(k==2) return 1;
	if(k==3) return 0;
	if(k==4) return x^1;
	return x;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	int inf = 1e7; 
	vector<vector<int>> dp(n+1, vector<int>(6, inf));
	string x, y;
	cin >> x >> y;
	vector<int> a(n+1), b(n+1);
	for(int i=0; i<n; ++i) {
		if(x[i]=='0') a[i+1] = 0;
		else a[i+1] = 1;
		if(y[i]=='0') b[i+1] = 0;
		else b[i+1] = 1;
	}
	vector<vector<pair<int, int>>> ways = {
		{{5,1}, {2,0}},
		{{5,1}, {3,0}},
		{{0,1}, {4,1}},
		{{1,1}, {4,1}},
		{{5,1}, {2,0}, {3,0}},
		{{0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {5,0}}
	};
	for(int i=0; i<=5; ++i) ways[i].push_back({i,0});
	dp[0][5] = 0;
	for(int i=1; i<=n; ++i) {
		for(int k=0; k<=5; ++k) {
			if(g(a[i],k) != b[i]) continue;
			for(auto[l, cost] : ways[k]) {
				dp[i][k] = min(dp[i][k], dp[i-1][l] + cost);
			}
		}	
	}
	auto get_ans = [&](int i) {
		int ans = inf;
		for(int k=0; k<=5; ++k) ans = min(ans, dp[i][k]);
		return ans;
	};
	cout << get_ans(n) << "\n";

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...