제출 #1296301

#제출 시각아이디문제언어결과실행 시간메모리
1296301takoshanavaLamps (JOI19_lamps)C++20
0 / 100
30 ms6452 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 = 1e5 + 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][k] = min(dp[i][k], 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...