Submission #108119

#	Time	Username	Problem	Language	Result	Execution time	Memory
108119		hugo_pm	Lamps (JOI19_lamps)	C++17	4 / 100	151 ms	67072 KiB

lamp

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

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borne = 1000*1000 + 5;
int dp[borne][2][3];
int len;
int cur[borne];
int cible[borne];

void calc(int dep, int isToggle, int set)
{
	int &rep = dp[dep][isToggle][set];
	rep = BIG;
	if (dep) {
		int vc = cur[dep];
		if (isToggle) vc ^= 1;
		if (set < 2) vc = set;
		if (vc != cible[dep]) { rep = BIG; return; }
	}
	
	if (dep == len) { rep = 0; return; }

	form(newTog, 2) form(newSet, 3) {
		int cx = dp[dep+1][newTog][newSet];
		if (newTog == 1 && isToggle == 0) ++cx;
		if (newSet != set && newSet != 2) ++cx;
		chmin(rep, cx);
	}
}

void solve()
{
	cin >> len;
	string s, t;
	cin >> s >> t;
	form(i, len) cur[i+1] = (s[i] == '0' ? 0 : 1);
	form(i, len) cible[i+1] = (t[i] == '0' ? 0 : 1);

	ford(i, len) form(a, 2) form(b, 3) calc(i+1,a,b);
	calc(0, 0, 2);
	cout << dp[0][0][2] << "\n";
}

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