#include <iostream>
using namespace std;
int dp[4][4][1000005],tpt[2][1000005];
int main()
{
int n;
string a,b;
cin >> n >> a >> b;
for (int j=0;j<4;j++)
{
for (int k=0;k<4;k++)
dp[j][k][0]=1e9;
}
dp[3][3][0]=0;
tpt[0][0]=1e9;
tpt[1][0]=1e9;
for (int i=0;i<=n;i++)
{
int mn=min(tpt[0][i],tpt[1][i]),md[4];
for (int j=0;j<4;j++)
md[j]=1e9;
md[2]=min(md[2],mn);
md[0]=min(md[0],tpt[0][i]);
md[1]=min(md[1],tpt[1][i]);
for (int j=0;j<4;j++)
{
for (int k=0;k<4;k++)
{
dp[j][k][i+1]=1e9;
mn=min(mn,dp[j][k][i]);
md[j]=min(md[j],dp[j][k][i]);
md[k]=min(md[k],dp[j][k][i]);
}
}
if (i==n)
{
printf("%d",mn);
return 0;
}
if (a[i]==b[i])
dp[3][3][i+1]=mn;
else
dp[2][3][i+1]=min(min(min(mn+1,md[2]),dp[2][3][i]),min(tpt[0][i],tpt[1][i]));
bool cur=b[i]-'0';
dp[!cur][2][i+1]=min(min(min(md[!cur]+1,md[2]+1),min(dp[!cur][2][i],mn+2)),tpt[!cur][i]);
dp[2][cur][i+1]=min(min(min(md[2]+1,md[cur]+1),min(dp[2][cur][i],mn+2)),tpt[cur][i]);
dp[cur][3][i+1]=min(min(min(md[cur]+1,md[3]+1),min(dp[cur][3][i],mn+2)),tpt[cur][i]);
tpt[cur][i+1]=1e9;
tpt[!cur][i+1]=min(min(min(tpt[!cur][i],mn+3),min(md[2],md[!cur])+2),min(min(dp[2][!cur][i],dp[!cur][2][i]),tpt[cur][i])+1);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
508 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
504 KB |
Output is correct |
| 13 |
Correct |
2 ms |
504 KB |
Output is correct |
| 14 |
Correct |
2 ms |
504 KB |
Output is correct |
| 15 |
Correct |
2 ms |
504 KB |
Output is correct |
| 16 |
Correct |
2 ms |
504 KB |
Output is correct |
| 17 |
Correct |
2 ms |
504 KB |
Output is correct |
| 18 |
Correct |
2 ms |
504 KB |
Output is correct |
| 19 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
508 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
504 KB |
Output is correct |
| 13 |
Correct |
2 ms |
504 KB |
Output is correct |
| 14 |
Correct |
2 ms |
504 KB |
Output is correct |
| 15 |
Correct |
2 ms |
504 KB |
Output is correct |
| 16 |
Correct |
2 ms |
504 KB |
Output is correct |
| 17 |
Correct |
2 ms |
504 KB |
Output is correct |
| 18 |
Correct |
2 ms |
504 KB |
Output is correct |
| 19 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
508 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
231 ms |
72904 KB |
Output is correct |
| 8 |
Correct |
230 ms |
72936 KB |
Output is correct |
| 9 |
Correct |
240 ms |
72924 KB |
Output is correct |
| 10 |
Correct |
230 ms |
72988 KB |
Output is correct |
| 11 |
Correct |
231 ms |
72884 KB |
Output is correct |
| 12 |
Correct |
244 ms |
73004 KB |
Output is correct |
| 13 |
Correct |
237 ms |
72964 KB |
Output is correct |
| 14 |
Correct |
233 ms |
72932 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
508 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
504 KB |
Output is correct |
| 13 |
Correct |
2 ms |
504 KB |
Output is correct |
| 14 |
Correct |
2 ms |
504 KB |
Output is correct |
| 15 |
Correct |
2 ms |
504 KB |
Output is correct |
| 16 |
Correct |
2 ms |
504 KB |
Output is correct |
| 17 |
Correct |
2 ms |
504 KB |
Output is correct |
| 18 |
Correct |
2 ms |
504 KB |
Output is correct |
| 19 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
