Submission #1005368

#TimeUsernameProblemLanguageResultExecution timeMemory
1005368AdamGSLamps (JOI19_lamps)C++17
4 / 100
20 ms26032 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=1e6+7, INF=1e9+7; int dp[LIM][3][2]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; string s, t; cin >> n >> s >> t; rep(i, 3) rep(j, 2) dp[0][i][j]=INF; dp[0][2][0]=0; rep(i, n) { rep(a, 3) rep(b, 2) dp[i+1][a][b]=INF; int x=0; if(s[i]!=t[i]) x=1; rep(a, 3) rep(b, 2) { int c=dp[i][a][b]; if(x==1 && b==0) ++c; dp[i+1][2][x]=min(dp[i+1][2][x], c); } x=0; if(t[i]!='0') x=1; rep(a, 3) rep(b, 2) { int c=dp[i][a][b]; if(a!=0) ++c; if(x==1 && b==0) ++c; dp[i+1][0][x]=min(dp[i+1][0][x], c); } x=0; if(t[i]!='1') x=1; rep(a, 3) rep(b, 2) { int c=dp[i][a][b]; if(a!=0) ++c; if(x==1 && b==0) ++c; dp[i+1][1][x]=min(dp[i+1][1][x], c); } } int ans=INF; rep(a, 3) rep(b, 2) ans=min(ans, dp[n][a][b]); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...