Submission #604113

#	Time	Username	Problem	Language	Result	Execution time	Memory
604113		jhnah917	Lamps (JOI19_lamps)	C++14	100 / 100	68 ms	33728 KiB

lamp

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

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