oj.uz

Submission #445727

# Submission time Handle Problem Language Result Execution time Memory
445727 2021-07-19T12:10:07 Z egod1537 Lamps (JOI19_lamps) C++14
4 / 100
 23 ms 8320 KB 
#include <bits/stdc++.h>

using namespace std;

int dp[1000001], sumA[4], sumB[4], mx[4];
bool prv[4];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int n; cin >> n;
	string A, B; cin >> A >> B;
	prv[1] = prv[3] = true;

	memset(dp, 0x3f3f3f3f, sizeof(dp));
	dp[0] = 0;

	for (int i = 1; i <= n; i++) {
		int& ret = dp[i];
		if (!prv[0] && B[i-1] == '1') sumA[0]++;
		if (prv[0] && B[i-1] == '0') sumB[0]++;
		ret = min(ret, mx[0]+sumA[0] + 1);
		prv[0] = B[i-1] == '1';

		if (prv[1] && B[i-1] == '0') sumA[1]++;
		if (!prv[1] && B[i-1] == '1') sumB[1]++;
		ret = min(ret, mx[1] + sumA[1] + 1);
		prv[1] = B[i-1] == '1';

		if (!prv[2] && A[i-1] == B[i-1]) sumA[2]++;
		if (prv[2] && A[i-1] != B[i-1]) sumB[2]++;
		ret = min(ret, mx[2] + sumA[2] + 1);
		prv[2] = A[i-1] == B[i-1];

		if (prv[3] && A[i-1] != B[i-1]) sumA[3]++;
		if (!prv[3] && A[i-1] == B[i-1]) sumB[3]++;
		ret = min(ret, mx[3] + sumA[3]);
		prv[3] = A[i-1] == B[i-1];

		for (int j = 0; j < 4; j++) mx[j] = min(mx[j], dp[i-1] - sumB[j]);
	}
	cout << dp[n];

	return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 41.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 2 ms 4172 KB Output is correct
4 Correct 2 ms 4172 KB Output is correct
5 Correct 2 ms 4172 KB Output is correct
6 Correct 2 ms 4172 KB Output is correct
7 Correct 19 ms 8220 KB Output is correct
8 Correct 21 ms 8320 KB Output is correct
9 Correct 22 ms 8288 KB Output is correct
10 Correct 23 ms 8220 KB Output is correct
11 Correct 22 ms 8288 KB Output is correct
12 Correct 19 ms 8300 KB Output is correct
13 Correct 21 ms 8220 KB Output is correct
14 Correct 20 ms 8296 KB Output is correct

Subtask #4
0 / 49.0

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