#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int d1[N],d2[N];
int mem[N];
string a,b;
int n;
int stat(int x)
{
// 0 01 1 10 2 00 3 11
if(a[x]==b[x])
return (a[x]=='0'?2:3);
return (a[x]=='0'?0:1);
}
int f1(int x,int y)
{
return d1[y]-(x?d1[x-1]:0)+(stat(x)<2);
}
int f2(int x,int y)
{
return d2[y]-(x?d2[x-1]:0)+(stat(x)>=2);
}
vector<int> cmp;
int pos[N],st[N];
int main()
{
cin >> n >> a >> b;
cmp.push_back(stat(0));
for(int i=1;i<n;i++)
{
if(stat(i)==cmp.back())
pos[i]=pos[i-1];
else
{
pos[i]=cmp.size();
st[cmp.size()]=i;
cmp.push_back(stat(i));
}
}
for(int i=1;i<n;i++)
{
d1[i]=(stat(i)!=stat(i-1)&&(stat(i)<2))+d1[i-1];
int mn=cmp[pos[i]],mx=cmp[pos[i]-1];
d2[i]=((stat(i)!=stat(i-1))&&(stat(i)>=2))+d2[i-1];
if(stat(i)!=stat(i-1))
{
if(pos[i]>=2&&cmp[pos[i]]==cmp[pos[i]-2] && a[i]!=a[i-1])
{
if(stat(i)<2)
d1[i]--;
if(stat(i)>=2)
d2[i]--;
}
}
}
/*for(int i=0;i<n;i++)
cout << d1[i] << " ";
cout << endl;
for(int i=0;i<n;i++)
cout << d2[i] << " ";
cout << endl;*/
for(int i=n-1;i>=0;i--)
{
mem[i]=(1<<30);
for(int j=i;j<n;j++)
{
mem[i]=min(mem[i],min(f1(i,j)+mem[j+1],1+f2(i,j)+mem[j+1]));
}
if(pos[i]+2<n)
{
int ind=st[pos[i]+2];
if(stat(ind)!=stat(ind-1))
{
if(cmp[ind]==cmp[i] && a[ind]!=a[ind-1])
{
for(int j=ind;j<n;j++)
{
if(stat(ind)<2)
d1[j]++;
if(stat(ind)>=2)
d2[j]++;
}
}
}
}
}
cout << mem[0] << endl;
}
Compilation message
lamp.cpp: In function 'int main()':
lamp.cpp:51:7: warning: unused variable 'mn' [-Wunused-variable]
int mn=cmp[pos[i]],mx=cmp[pos[i]-1];
^~
lamp.cpp:51:22: warning: unused variable 'mx' [-Wunused-variable]
int mn=cmp[pos[i]],mx=cmp[pos[i]-1];
^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
380 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
380 KB |
Output is correct |
| 21 |
Correct |
2 ms |
380 KB |
Output is correct |
| 22 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
380 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
380 KB |
Output is correct |
| 21 |
Correct |
2 ms |
380 KB |
Output is correct |
| 22 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
424 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Runtime error |
154 ms |
28460 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
380 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
380 KB |
Output is correct |
| 21 |
Correct |
2 ms |
380 KB |
Output is correct |
| 22 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 23 |
Halted |
0 ms |
0 KB |
- |
