# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
493170 |
2021-12-10T09:24:02 Z |
Lukap |
Lamps (JOI19_lamps) |
C++14 |
|
396 ms |
41488 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
const int INF = 1e9 + 7;
int n;
int a[MAXN], b[MAXN];
int dp[MAXN][4][2];
int dodaj (int i, int x, int y, int fx, int fy) {
if (a[i] == b[i]) {
if (x == 3 && fx == 0) return INF;
if (x >= 1 && x <= 2 && x % 2 != b[i] && fx == 0) return INF;
if (x == 0 && fx == 1) return INF;
if (x >= 1 && x <= 2 && x % 2 == b[i] && fx == 1) return INF;
}
else {
if (x >= 1 && x <= 2 && x % 2 != b[i] && fx == 0) return INF;
if (x == 0 && fx == 0) return INF;
if (x >= 1 && x <= 2 && x % 2 == b[i] && fx == 1) return INF;
}
if (fx == 0) {
if (x == 3) return INF;
else if (x != 0 && x != y) return 1;
else return 0;
}
else {
if (fy == 0) {
if (x != 3) return INF;
return 1;
}
else {
if (x == 3) return 1;
else if (x != 0 && x != y) return 1;
else return 0;
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n + 1; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 2; k++) dp[i][j][k] = INF;
}
}
for (int i = 0; i < n; i++) {
char c;
cin >> c;
a[i + 1] = c - '0';
}
for (int i = 0; i < n; i++) {
char c;
cin >> c;
b[i + 1] = c - '0';
}
dp[0][0][0] = 0;
for (int i = 1; i < n + 1; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 2; k++) {
for (int l = 0; l < 4; l++) {
for (int m = 0; m < 2; m++) dp[i][j][k] = min (dp[i][j][k], dp[i - 1][l][m] + dodaj (i, j, l, k, m));
}
// cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k] << "\n";
}
}
}
int rj = INF;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 2; j++) rj = min (rj, dp[n][i][j]);
}
cout << rj;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
236 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
324 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
236 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
324 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
356 ms |
41372 KB |
Output is correct |
8 |
Correct |
344 ms |
41396 KB |
Output is correct |
9 |
Correct |
348 ms |
41412 KB |
Output is correct |
10 |
Correct |
355 ms |
41488 KB |
Output is correct |
11 |
Correct |
396 ms |
41488 KB |
Output is correct |
12 |
Correct |
312 ms |
41284 KB |
Output is correct |
13 |
Correct |
352 ms |
41460 KB |
Output is correct |
14 |
Correct |
351 ms |
41392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
236 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
312 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
324 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |