#include <iostream>
using namespace std;
int n, dp[1000010][4];
string s, t;
int main() {
cin >> n >> s >> t;
for (int i = 0; i <= n; i++) for (int j = 0; j < 4; j++) dp[i][j] = 1e9;
dp[0][0] = 0;
s = " "+s; t = " "+t;
for (int i = 1; i <= n; i++) {
if (s[i] == t[i]) dp[i][0] = min(min(dp[i-1][0],dp[i-1][1]),min(dp[i-1][2],dp[i-1][3]));
if (t[i] == '0') dp[i][1] = min(min(dp[i-1][0]+1,dp[i-1][1]),min(dp[i-1][2]+1,dp[i-1][3]+1));
if (t[i] == '1') dp[i][2] = min(min(dp[i-1][0]+1,dp[i-1][1]+1),min(dp[i-1][2],dp[i-1][3]+1));
if (s[i] != t[i]) dp[i][3] = min(min(dp[i-1][0]+1,dp[i-1][1]+1),min(dp[i-1][2]+1,dp[i-1][3]));
}
cout << min(min(dp[n][0],dp[n][1]),min(dp[n][2],dp[n][3])) << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
456 KB |
Output is correct |
| 11 |
Correct |
1 ms |
504 KB |
Output is correct |
| 12 |
Correct |
1 ms |
452 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
848 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
456 KB |
Output is correct |
| 11 |
Correct |
1 ms |
504 KB |
Output is correct |
| 12 |
Correct |
1 ms |
452 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
848 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
592 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
504 KB |
Output is correct |
| 7 |
Correct |
38 ms |
20996 KB |
Output is correct |
| 8 |
Correct |
36 ms |
21060 KB |
Output is correct |
| 9 |
Correct |
35 ms |
21052 KB |
Output is correct |
| 10 |
Correct |
36 ms |
21052 KB |
Output is correct |
| 11 |
Correct |
36 ms |
20964 KB |
Output is correct |
| 12 |
Correct |
36 ms |
21052 KB |
Output is correct |
| 13 |
Correct |
36 ms |
20988 KB |
Output is correct |
| 14 |
Correct |
37 ms |
21052 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
336 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
1 ms |
456 KB |
Output is correct |
| 11 |
Correct |
1 ms |
504 KB |
Output is correct |
| 12 |
Correct |
1 ms |
452 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
848 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
