#include<bits/stdc++.h>
using namespace std;
constexpr int maxn = 1e6+10;
bool mark[maxn];
string a, b;
int dp[3], new_dp[3];
// 0 -> melhor com fim branco
// 1 -> fim preto
// 2 -> fim sem fazer nd
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
cin >> a >> b;
dp[0] = dp[1] = 0x3f3f3f3f;
for(int i = 0; i < n; i++) {
new_dp[0] = min(dp[0] + (b[i]=='0' && (i==0||b[i-1]=='1')), min(dp[2],dp[1]) + 1 + (b[i] == '0'));
new_dp[1] = min(dp[1] + (b[i]=='1' && (i==0||b[i-1]=='0')), min(dp[2],dp[0]) + 1 + (b[i] == '1'));
new_dp[2] = dp[2] + (a[i]!=b[i]&&(i==0||a[i-1]==b[i-1]));
// dp[2]++;
if((a[i]!=b[i]&&(i==0||a[i-1]==b[i-1])) || a[i] == b[i])
new_dp[2] = min(new_dp[2], min(dp[0], dp[1]) + (a[i] != b[i]));
swap(dp[0], new_dp[0]);
swap(dp[1], new_dp[1]);
swap(dp[2], new_dp[2]);
// printf("%d: %d %d %d\n", i, dp[0], dp[1], dp[2]);
}
printf("%d\n", min({dp[0], dp[1], dp[2]}));
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
13 ms |
2844 KB |
Output is correct |
| 8 |
Correct |
12 ms |
2844 KB |
Output is correct |
| 9 |
Correct |
12 ms |
2844 KB |
Output is correct |
| 10 |
Correct |
12 ms |
2844 KB |
Output is correct |
| 11 |
Correct |
12 ms |
2844 KB |
Output is correct |
| 12 |
Correct |
11 ms |
2844 KB |
Output is correct |
| 13 |
Correct |
11 ms |
2844 KB |
Output is correct |
| 14 |
Correct |
12 ms |
2844 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
0 ms |
384 KB |
Output is correct |
| 10 |
Correct |
0 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
