제출 #867240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867240		Dawnlight	Lamps (JOI19_lamps)	C++14	100 / 100	54 ms	16208 KiB

lamp

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49