Submission #1207131

#TimeUsernameProblemLanguageResultExecution timeMemory
1207131VMaksimoski008Lamps (JOI19_lamps)C++20
100 / 100
54 ms4224 KiB
#include <bits/stdc++.h> #define ar array //#define int long long using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const ll inf = 1e18; const int N = 1e5 + 5; signed main() { int n, ans=1e9; cin >> n; string a, b; cin >> a >> b; a = "." + a; b = "." + b; int dp[3][2], ndp[3][2]; for(int i=0; i<3; i++) for(int j=0; j<2; j++) dp[i][j] = 1e9; dp[0][0] = 0; for(int i=1; i<=n; i++) { for(int j=0; j<3; j++) { for(int k=0; k<2; k++) { ndp[j][k] = 1e9; int v = a[i] - '0'; if(j) v = j - 1; if(k) v ^= 1; if(v != b[i] - '0') continue; for(int pj=0; pj<3; pj++) for(int pk=0; pk<2; pk++) ndp[j][k] = min(ndp[j][k], dp[pj][pk] + (j && pj != j) + (k && !pk)); } } swap(dp, ndp); } for(int i=0; i<3; i++) for(int j=0; j<2; j++) ans = min(ans, dp[i][j]); 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...