Submission #376170

#	Time	Username	Problem	Language	Result	Execution time	Memory
376170		Kevin_Zhang_TW	Lamps (JOI19_lamps)	C++17	4 / 100	12 ms	10220 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 1000010, inf = MAX_N;

int n;
char a[MAX_N], b[MAX_N];
int va[MAX_N], vb[MAX_N], pfa[MAX_N], pfb[MAX_N], dp[MAX_N], dif[MAX_N];

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> a+1 >> b+1;
	for (int i = 1;i <= n;++i) a[i] -= '0', b[i] -= '0';
	++n;
	for (int i = n;i >= 1;--i) {
		va[i] = a[i] ^ a[i-1];
		vb[i] = b[i] ^ b[i-1];
	}

	if (accumulate(va, va+n+1, 0) == 0)
		return cout << accumulate(vb, vb + n + 1, 0) / 2 << '\n', 0;

	if (n > 2000) return -1;


	for (int i = 1;i <= n;++i) {
		pfa[i] = pfa[i-1] + va[i];
		pfb[i] = pfb[i-1] + vb[i];
		dif[i] = dif[i-1] + (va[i] != vb[i]);
	}

	debug(va, va+n+1), debug(vb, vb+n+1);
	debug(dif, dif+n+1);

	for (int i = 1;i <= n;++i) {
		dp[i] = dif[i] + 1;
		for (int j = 0;j < i;++j) {
			if ( (pfa[i] - pfa[j]) % 2 == 0)
				chmin(dp[i], dp[j] + 2 +
						(!vb[i] + !vb[j+1] + pfb[i-1] - pfb[j+1]));
		}
		for (int j = 0;j < i;++j) {
			chmin(dp[i], dp[j] + dif[i] - dif[j]);
		}
		DE(i, dp[i]);
	}

	cout << dp[n] / 2 << '\n';
}

Compilation message (stderr)

lamp.cpp: In function 'int32_t main()':
lamp.cpp:25:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |  cin >> n >> a+1 >> b+1;
      |              ~^~
lamp.cpp:25:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |  cin >> n >> a+1 >> b+1;
      |                     ~^~
lamp.cpp:15:20: warning: left operand of comma operator has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
lamp.cpp:45:2: note: in expansion of macro 'debug'
   45 |  debug(va, va+n+1), debug(vb, vb+n+1);
      |  ^~~~~
lamp.cpp:45:38: warning: right operand of comma operator has no effect [-Wunused-value]
   45 |  debug(va, va+n+1), debug(vb, vb+n+1);
      |                                      ^
lamp.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
lamp.cpp:46:2: note: in expansion of macro 'debug'
   46 |  debug(dif, dif+n+1);
      |  ^~~~~
lamp.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
lamp.cpp:58:3: note: in expansion of macro 'DE'
   58 |   DE(i, dp[i]);
      |   ^~

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