Submission #869575

#	Time	Username	Problem	Language	Result	Execution time	Memory
869575		NK_	Lamps (JOI19_lamps)	C++17	100 / 100	115 ms	75176 KiB

lamp

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
using str = string;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;
	str S; cin >> S;
	str T; cin >> T;

	V<vi> dp(N+1, vi(8, MOD)); // [flip][set 0][set 1]

	dp[0][0] = 0;
	for(int i = 0; i < N; i++) for(int x = 0; x < 8; x++) if (dp[i][x] != MOD) {
		if (x & (x >> 1) & 1) continue;
		// cout << i << " " << x << " " << dp[i][x] << endl;

		for(int y = 0; y < 8; y++) {
			if (y & (y >> 1) & 1) continue;
			int cost = __builtin_popcount(x ^ y);

			char c = S[i];
			if ((y >> 0) & 1) c = '1';
			if ((y >> 1) & 1) c = '0';
			if ((y >> 2) & 1) c = '0' + '1' - c;

			// cout << y << " " << c << endl;

			if (c == T[i]) dp[i+1][y] = min(dp[i][x] + cost, dp[i+1][y]);
		}
	}

	int ans = MOD;
	for(int i = 0; i < 8; i++) ans = min(ans, dp.back()[i] + __builtin_popcount(i));

	cout << ans / 2 << nl;

	exit(0-0);
} 	 

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