Submission #104755

#	Time	Username	Problem	Language	Result	Execution time	Memory
104755		mzhao	Lamps (JOI19_lamps)	C++11	4 / 100	22 ms	10324 KiB

lamp

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

#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif

#define MN 1000009

int N, A[MN], B[MN], ans, dp[MN][2]; // finish with opposite
string AA, BB;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> AA >> BB;
	bool SUB3 = 1;
	for (int i = 1; i <= N; i++) {
		A[i] = AA[i-1] == '1';
		B[i] = BB[i-1] == '1';
		if (A[i]) SUB3 = 0;
	}
	if (SUB3) {
		for (int i = 1, C; i <= N; i++) {
			if ((!i || B[i] != B[i-1]) && B[i]) ans++;
		}
		printf("%d\n", ans);
		return 0;
	}
	assert(N <= 2000);
	for (int i = 1; i <= N; i++) dp[i][0] = dp[i][1] = 1e8;
	for (int i = 1; i <= N; i++) {
		dp[i][0] = dp[i-1][0]+(A[i] != B[i]);
		dp[i][1] = dp[i-1][1]+(A[i] == B[i]);
		for (int j = i-1; j >= 0; j--) {
			dp[i][0] = min(dp[i][0], dp[j][0]+1);
			if (B[i] != B[j]) break;
		}
		for (int j = i-1; j >= 0; j--) {
			dp[i][1] = min(dp[i][1], dp[j][1]+1);
			if (B[i] == B[j]) break;
		}
		int cur = 0;
		// change everything to be correct
		for (int j = i; j > 0; j--) {
			if (A[j] != B[j]) cur++;
			dp[i][0] = min(dp[i][0], dp[j-1][0]+cur);
		}
		// change everything to be opposite
		cur = 0;
		for (int j = i; j > 0; j--) {
			if (A[j] == B[j]) cur++;
			dp[i][1] = min(dp[i][1], dp[j-1][1]+cur);
		}
		dp[i][0] = min(dp[i][0], dp[i][1]+1);
		dp[i][1] = min(dp[i][1], dp[i][0]+1);
	}
	printf("%d\n", min(dp[N][0], dp[N][1]+1));
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:25:19: warning: unused variable 'C' [-Wunused-variable]
   for (int i = 1, C; i <= N; i++) {
                   ^

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