Submission #210595

#TimeUsernameProblemLanguageResultExecution timeMemory
210595Mamnoon_SiamLamps (JOI19_lamps)C++17
100 / 100
189 ms41620 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ii = pair<int, int>; using vi = vector<int>; const int N = 1e6 + 6; // msk = reset|set|toggle int apply(int x, int msk) { int ret = x; if(msk & 4) ret = 0; if(msk & 2) ret = 1; if(msk & 1) ret ^= 1; return ret; } int dp[N][1 << 3]; int n; vi A, B; int main(int argc, char const *argv[]) { cin.sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit); #ifdef LOCAL freopen("in", "r", stdin); #endif cin >> n; #define read(v) { string s; cin >> s; \ for(int i = 0; i < n; i++) v.emplace_back(s[i] - '0'); } read(A); read(B); for(int u = 0; u < 8; u++) dp[n][u] = __builtin_popcount(u); for(int i = n-1; i >= 0; i--) { for(int u = 0; u < 8; u++) dp[i][u] = 1e9; for(int u = 0; u < 8; u++) if((u & 6) != 6) { for(int v = 0; v < 8; v++) if((v & 6) != 6) { if(apply(A[i], v) == B[i]) { dp[i][u] = min(dp[i][u], __builtin_popcount(u ^ v) + dp[i+1][v]); } } } } cout << dp[0][0] / 2 << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...