Submission #1028373

#TimeUsernameProblemLanguageResultExecution timeMemory
1028373BlagojLamps (JOI19_lamps)C++17
100 / 100
64 ms51452 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define all(x) (x).begin(), (x).end() int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; string s1, s2; cin >> s1 >> s2; s1 = "." + s1; s2 = "." + s2; ll dp[n + 10][3][2]; for (int i = 0; i <= n; i++) for (int j = 0; j < 3; j++) for (int l = 0; l < 2; l++) dp[i][j][l] = 1e12; dp[0][0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < 3; j++) { for (int l = 0; l < 2; l++) { int val = s1[i] - '0'; if (j == 1) val = 0; if (j == 2) val = 1; if (l == 1) val ^= 1; if (val != s2[i] - '0') continue; for (int prevJ = 0; prevJ < 3; prevJ++) for (int prevL = 0; prevL < 2; prevL++) dp[i][j][l] = min(dp[i][j][l], dp[i - 1][prevJ][prevL] + (j > 0 && j != prevJ) + (l > 0 && l != prevL)); } } } ll ans = 1e12; for (int j = 0; j < 3; j++) for (int l = 0; l < 2; l++) ans = min(ans, dp[n][j][l]); 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...