Submission #210119

#	Time	Username	Problem	Language	Result	Execution time	Memory
210119		DrumpfTheGodEmperor	Lamps (JOI19_lamps)	C++14	100 / 100	123 ms	35644 KiB

lamp

#include <bits/stdc++.h>
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 1e6 + 5;
int n, dp[N][2][2][2];
string a, b;
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> a >> b;
//	Strategy: Use the first 2 operations to turn the sequence into alternating 0s and 1s segments, then
//	in each segment use operation 3 to make 'em gud.
//	dp[i][2][2][2]: Lamp i, currently wot's the color, dood we pay for it, wot's the flip status.
	a = " " + a;
	b = " " + b;
	memset(dp, 63, sizeof dp);
	dp[0][0][0][0] = 0;
	dp[0][1][0][0] = 0;
	
	fw (i, 0, n) fw (j, 0, 2) fw (paid, 0, 2) fw (k, 0, 2) if (dp[i][j][paid][k] != inf) {
		int final = j ^ k;
		if (i && final != b[i] - '0') continue;
//		cout << "dp[" << i << "][" << j << "][" << paid << "][" << k << "] = " << dp[i][j][paid][k] << "\n";
		
		fw (nxtj, 0, 2) fw (nxtk, 0, 2) {
			int cost = 0, nxtPaid = 0;
			if (nxtj != j) {
				if (nxtj == a[i + 1] - '0') nxtPaid = 0, cost = 0;
				else nxtPaid = 1, cost = 1;
			} else {
				if (paid) cost = 0, nxtPaid = 1;
				else {
					if (a[i + 1] - '0' == nxtj) cost = 0, nxtPaid = 0;
					else cost = 1, nxtPaid = 1;
				}
			}
			int costk = 0;
			if (k == 0 && nxtk == 1) costk = 1;
			dp[i + 1][nxtj][nxtPaid][nxtk] = min(dp[i + 1][nxtj][nxtPaid][nxtk], dp[i][j][paid][k] + cost + costk);
		}
	}
	int ans = inf;
	fw (j, 0, 2) fw (paid, 0, 2) fw (k, 0, 2) {
		int final = j ^ k;
		if (final != b[n] - '0') continue;
//		cout << "dp[" << n << "][" << j << "][" << paid << "][" << k << "] = " << dp[n][j][paid][k] << "\n";
		ans = min(ans, dp[n][j][paid][k]);
	}
	cout << ans;
	return 0;
}

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