Submission #1013911

#TimeUsernameProblemLanguageResultExecution timeMemory
1013911vjudge1Lamps (JOI19_lamps)C++17
100 / 100
60 ms51624 KiB
#include<bits/stdc++.h> using namespace std; #define int long long bool make(int j,int k,int a,int b){ if(j!=2){ a=j; } a^=k; return (a==b); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; string a; string b; cin >> a; cin >> b; int DP[n][3][2]; int lim=1e9; for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ for(int k=0;k<2;k++){ DP[i][j][k]=lim; } } } for(int j=0;j<3;j++){ for(int k=0;k<2;k++){ if(make(j,k,a[0]-'0',b[0]-'0')){ DP[0][j][k]=(j!=2)+(k!=0); } } } for(int i=0;i<n-1;i++){ for(int j=0;j<3;j++){ for(int k=0;k<2;k++){ if(DP[i][j][k]==lim){ continue; } for(int j1=0;j1<3;j1++){ for(int k1=0;k1<2;k1++){ if(make(j1,k1,a[i+1]-'0',b[i+1]-'0')){ DP[i+1][j1][k1]=min(DP[i+1][j1][k1],DP[i][j][k]+(j1!=2&&j1!=j)+(k1!=0&&k1!=k)); } } } } } } int ans=1e9; for(int j=0;j<3;j++){ for(int k=0;k<2;k++){ ans=min(ans,DP[n-1][j][k]); } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...