Submission #1306367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306367		vlomaczk	Lamps (JOI19_lamps)	C++20	100 / 100	81 ms	65148 KiB

lamp

#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;
}

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