제출 #604113

#제출 시각아이디문제언어결과실행 시간메모리
604113jhnah917Lamps (JOI19_lamps)C++14
100 / 100
68 ms33728 KiB
#include <bits/stdc++.h>
using namespace std;

int N, A[1010101], B[1010101], C[1010101][3], D[1010101][3];

int SetCost(int idx, int prv, int now){ return now != 2 && prv != now; }
int FlipCost(int idx, int prv, int now){ return C[idx-1][prv] == 0 && C[idx][now] == 1; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++){ char c; cin >> c; A[i] = c - '0'; }
    for(int i=1; i<=N; i++){ char c; cin >> c; B[i] = c - '0'; }
    for(int i=1; i<=N; i++) C[i][0] = B[i] != 0, C[i][1] = B[i] != 1, C[i][2] = A[i] != B[i];

    memset(D, 0x3f, sizeof D);
    D[1][0] = 1 + C[1][0]; D[1][1] = 1 + C[1][1]; D[1][2] = C[1][2];
    for(int i=2; i<=N; i++){
        for(int now=0; now<3; now++) for(int prv=0; prv<3; prv++) D[i][now] = min(D[i][now], D[i-1][prv] + SetCost(i, prv, now) + FlipCost(i, prv, now));
    }
    cout << *min_element(D[N], D[N]+3);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...