# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
659924 |
2022-11-19T17:37:02 Z |
cristi_a |
Lamps (JOI19_lamps) |
C++17 |
|
23 ms |
19904 KB |
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6;
const int inf = 1e9;
int dp[nmax+5][4];
// 0 nimic
// 1 off
// 2 on
// 3 toggle
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; string a, b; cin >> n >> a >> b;
a = " " + a; b = " " + b;
for(int i=0; i<=n; i++)
for(int j=0; j<=3; j++)
dp[i][j] = inf;
dp[0][0] = 0;
for(int i=1; i<=n; i++) {
if(a[i] == '0' and b[i] == '0') {
dp[i][0] = min({dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3]});
dp[i][1] = min({dp[i-1][0] + 1, dp[i-1][1], dp[i-1][2] + 1, dp[i-1][3] + 1});
}
else if(a[i] == '0' and b[i] == '1') {
dp[i][2] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2], dp[i-1][3] + 1});
dp[i][3] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2] + 1, dp[i-1][3]});
}
else if(a[i] == '1' and b[i] == '0') {
dp[i][1] = min({dp[i-1][0] + 1, dp[i-1][1], dp[i-1][2] + 1, dp[i-1][3] + 1});
dp[i][3] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2] + 1, dp[i-1][3]});
}
else if(a[i] == '1' and b[i] == '1') {
dp[i][0] = min({dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3]});
dp[i][2] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2], dp[i-1][3] + 1});
}
}
cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]});
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
328 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
22 ms |
19812 KB |
Output is correct |
8 |
Correct |
23 ms |
19848 KB |
Output is correct |
9 |
Correct |
23 ms |
19896 KB |
Output is correct |
10 |
Correct |
23 ms |
19812 KB |
Output is correct |
11 |
Correct |
22 ms |
19848 KB |
Output is correct |
12 |
Correct |
21 ms |
19904 KB |
Output is correct |
13 |
Correct |
22 ms |
19864 KB |
Output is correct |
14 |
Correct |
21 ms |
19784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |