Submission #867240

#TimeUsernameProblemLanguageResultExecution timeMemory
867240DawnlightLamps (JOI19_lamps)C++14
100 / 100
54 ms16208 KiB
#include <bits/stdc++.h>
#define ll long long
#define SZ(X) (int)(X.size())
#define MAX 1000006
using namespace std;

int len;
bool orig[MAX], targ[MAX];
int dp[MAX][3]; //  dp[i][3] answer for prefix i if [turn off, turn on, none] operation is used on the last letter

bool needXor(int loc, int op){
    return (op == 2 ? orig[loc] != targ[loc] : op != targ[loc]);
}

void input(bool & loc){
    char c;
    cin >> c;
    loc = c-'0';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> len;
    for (int i = 1; i <= len; i++)
        input(orig[i]);
    for (int i = 1; i <= len; i++)
        input(targ[i]);
    
    dp[0][0] = dp[0][1] = MAX; // on/off operations should greedily come before xor operations
    for (int i = 1; i <= len; i++){ // on/off operations won't overlap; xor operations won't overlap
        for (int j : {0, 1, 2}){ // for this location
            dp[i][j] = MAX;
            for (int k : {0, 1, 2}){ // for previous location
                int res = dp[i-1][k] + (k != j && j != 2) + (!needXor(i-1, k) && needXor(i, j)); // cost of (starting new on/off operation) + (starting new xor op)
                dp[i][j] = min(res, dp[i][j]);
            }
        }
    }
    cout << min({dp[len][0], dp[len][1], dp[len][2]}) << "\n";
    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...