Submission #1116776

#TimeUsernameProblemLanguageResultExecution timeMemory
1116776firewaterLamps (JOI19_lamps)C++14
100 / 100
68 ms51788 KiB
#include<bits/stdc++.h> #define N 1001000 using namespace std; int n,ans,a[N],b[N],f[N][5][2]; char s1[N],s2[N]; int main() { scanf("%d%s%s",&n,s1+1,s2+1); for(int i=1;i<=n;++i) a[i]=s2[i]-'0'+1,b[i]=(s1[i]!=s2[i]); memset(f,127/3,sizeof(f)); f[0][0][0]=0; for(int i=1;i<=n;++i) for(int j=0;j<=2;++j) for(int k=0;k<=1;++k){ f[i][0][b[i]]=min(f[i][0][b[i]],f[i-1][j][k]+(b[i]&&(b[i]!=k))); if(j){ f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+(a[i]!=j&&a[i]!=a[i-1])); f[i][j%2+1][!k]=min(f[i][j%2+1][!k],f[i-1][j][k]+(!k)+(a[i]==j&&a[i]==a[i-1])); } f[i][a[i]][k]=min(f[i][a[i]][k],f[i-1][j][k]+1); } ans=f[0][0][1]; for(int j=0;j<=2;++j) for(int k=0;k<=1;++k) ans=min(ans,f[n][j][k]); printf("%d\n",ans); return 0; }

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:8:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |   scanf("%d%s%s",&n,s1+1,s2+1);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...