Submission #384794

#TimeUsernameProblemLanguageResultExecution timeMemory
384794kostia244Lamps (JOI19_lamps)C++17
4 / 100
60 ms26044 KiB
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 12; int dp[maxn][3][2]; void minq(int &a, int b) { a = min(a, b); } int main() { cin.tie(0)->sync_with_stdio(0); int n; string a, b; cin >> n >> a >> b; memset(dp, 0x3f, sizeof dp); dp[0][0][0] = 0; for(int i = 0; i < n; i++) { for(int lst = 0; lst < 3; lst++) { dp[i][lst][0] = min(dp[i][lst][0], dp[i][lst][1]); dp[i][lst][1] = min(dp[i][lst][1], dp[i][lst][0]+1); for(int rev = 0; rev < 2; rev++) { int cur = (a[i]-'0')^rev; int targ = b[i]-'0'; if((cur == targ && !lst) || lst-1 == targ) minq(dp[i+1][lst][rev], dp[i][lst][rev]); if(cur == targ) minq(dp[i+1][0][rev], dp[i][lst][rev]); minq(dp[i+1][1+targ][rev], dp[i][lst][rev]+1); } } } int ans = 69<<20; for(int i = 0; i < 3; i++) for(int j = 0; j < 2; j++) ans = min(dp[n][i][j], ans); 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...