Submission #1296303

#TimeUsernameProblemLanguageResultExecution timeMemory
1296303takoshanavaLamps (JOI19_lamps)C++20
100 / 100
77 ms41604 KiB
#include <bits/stdc++.h> #define int long long #define pb push_back #define fs first #define sc second using namespace std; const int N = 1e6 + 5; int dp[N][5]; vector<int> vec = {0, 1, 2}; signed main() { int n; string a, b; cin >> n >> a >> b; for(int i = 0; i < N; i++){ for(int j = 0; j < 5; j++) dp[i][j] = N; } dp[0][2] = 0; for(int i = 1; i <= n; i++){ for(auto k:vec){ char p = k + '0'; if (i > 1 and k == 2) p = a[i - 2]; for(auto v:vec){ int cnt = dp[i - 1][k]; if(k != v and v != 2) cnt++; char c = v + '0'; if(v == 2) c = a[i - 1]; if(c != b[i - 1] and (i == 1 or p == b[i - 2])) cnt++; dp[i][v] = min(dp[i][v], cnt); } } } int ans = N; for(int i = 0; i < 3; i++) ans = min(ans, dp[n][i]); cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...