oj.uz

Submission #104755

# Submission time Handle Problem Language Result Execution time Memory
104755 2019-04-09T06:40:22 Z mzhao Lamps (JOI19_lamps) C++11
4 / 100
 22 ms 10324 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Incorrect 2 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Incorrect 2 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 304 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 15 ms 10324 KB Output is correct
8 Correct 21 ms 10324 KB Output is correct
9 Correct 21 ms 10316 KB Output is correct
10 Correct 19 ms 10324 KB Output is correct
11 Correct 20 ms 10324 KB Output is correct
12 Correct 17 ms 10324 KB Output is correct
13 Correct 22 ms 10304 KB Output is correct
14 Correct 18 ms 10324 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Incorrect 2 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -