제출 #1163393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163393		Math4Life2020	Lamps (JOI19_lamps)	C++20	100 / 100	70 ms	65500 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N; cin >> N;
    string A,B; cin >> A >> B;
    vector<bool> va,vb;
    va.push_back(0); vb.push_back(0);
    for (ll i=0;i<N;i++) {
        va.push_back(A[i]=='1');
        vb.push_back(B[i]=='1');
    }
    va.push_back(0); vb.push_back(0);
    vector<ll> dp0(N+2,INF);
    vector<ll> dpa(N+2,INF);
    vector<ll> dpa2(N+2,INF);
    vector<ll> dpa3(N+2,INF);
    vector<ll> dpb(N+2,INF);
    vector<ll> dpba(N+2,INF);
    vector<ll> dpba2(N+2,INF);
    vector<ll> dpba3(N+2,INF);
    dp0[0]=0;
    for (ll i=0;i<(N+1);i++) {
        bool isa = va[i]^va[i+1];
        bool isb = vb[i]^vb[i+1];
        if (!isa && !isb) {
            dp0[i+1]=dp0[i];
            dpa[i+1]=dpa[i];
            dpa2[i+1]=dpa2[i];
            dpa3[i+1]=dpa3[i];
            dpb[i+1]=dpb[i];
            dpba[i+1]=dpba[i];
            dpba2[i+1]=dpba2[i];
            dpba3[i+1]=dpba3[i];
            dp0[i+1]=min(dp0[i+1],dpa[i+1]);
            dp0[i+1]=min(dp0[i+1],dpa2[i+1]);
            dp0[i+1]=min(dp0[i+1],dpa3[i+1]);
            dp0[i+1]=min(dp0[i+1],dpb[i+1]);
            dp0[i+1]=min(dp0[i+1],dpba[i+1]);
            dp0[i+1]=min(dp0[i+1],dpba2[i+1]);
            dp0[i+1]=min(dp0[i+1],dpba3[i+1]);
            continue;
        }
        if (!isa && isb) {
            dp0[i+1]=dp0[i]+1;
            dpa[i+1]=dpa[i]+1;
            dpa2[i+1]=dpa2[i]+1;
            dpa3[i+1]=dpa3[i]+1;
            dpb[i+1]=min(dpb[i]+1,dp0[i]+1);
            dpba[i+1]=dpba[i]+1;
            dpba2[i+1]=dpba2[i]+1;
            dpba3[i+1]=dpba3[i]+1;
            dp0[i+1]=min(dp0[i+1],dpba2[i]-1);
            dp0[i+1]=min(dp0[i+1],dpa3[i]-1);
            dp0[i+1]=min(dp0[i+1],dpa[i+1]);
            dp0[i+1]=min(dp0[i+1],dpa2[i+1]);
            dp0[i+1]=min(dp0[i+1],dpa3[i+1]);
            dp0[i+1]=min(dp0[i+1],dpb[i+1]);
            dp0[i+1]=min(dp0[i+1],dpba[i+1]);
            dp0[i+1]=min(dp0[i+1],dpba2[i+1]);
            dp0[i+1]=min(dp0[i+1],dpba3[i+1]);
            continue;
        }
        //else: isa
        dp0[i+1]=dp0[i]+1;
        dpa[i+1]=min(dp0[i]+1,dpa[i]+1);
        dpa2[i+1]=min(min(dpa[i]+1,dpa2[i]+1),dpa3[i]-1);
        dpa3[i+1]=min(dpa2[i]+1,dpa3[i]+1);
        dpb[i+1]=dpb[i]+1;
        dpba[i+1]=min(dpb[i]+1,dpba[i]+1);
        dpba2[i+1]=min(min(dpba[i]+1,dpba2[i]+1),dpba3[i]-1);
        dpba3[i+1]=min(dpba2[i]+1,dpba3[i]+1);
        dp0[i+1]=min(dp0[i+1],dpba2[i]-1);
        dp0[i+1]=min(dp0[i+1],dpa[i+1]);
        dp0[i+1]=min(dp0[i+1],dpa2[i+1]);
        dp0[i+1]=min(dp0[i+1],dpa3[i+1]);
        dp0[i+1]=min(dp0[i+1],dpb[i+1]);
        dp0[i+1]=min(dp0[i+1],dpba[i+1]);
        dp0[i+1]=min(dp0[i+1],dpba2[i+1]);
        dp0[i+1]=min(dp0[i+1],dpba3[i+1]);
        //process isb
        if (isb) {
            dp0[i+1]++;
            dpa[i+1]++;
            dpa2[i+1]++;
            dpa3[i+1]++;
            dpb[i+1]++;
            dpba[i+1]++;
            dpba2[i+1]++;
            dpba3[i+1]++;
            dp0[i+1]=min(dp0[i+1],dp0[i]);
        }
        dp0[i+1]=min(dp0[i+1],dpa[i+1]);
        dp0[i+1]=min(dp0[i+1],dpa2[i+1]);
        dp0[i+1]=min(dp0[i+1],dpa3[i+1]);
        dp0[i+1]=min(dp0[i+1],dpb[i+1]);
        dp0[i+1]=min(dp0[i+1],dpba[i+1]);
        dp0[i+1]=min(dp0[i+1],dpba2[i+1]);
        dp0[i+1]=min(dp0[i+1],dpba3[i+1]);
    }
    // for (ll i=0;i<(N+2);i++) {
    //     cout << "i="<<i<<"\n";
    //     cout << "dp0="<<dp0[i]<<"\n";
    //     cout << "dpa="<<dpa[i]<<"\n";
    //     cout << "dpa2="<<dpa2[i]<<"\n";
    //     cout << "dpa3="<<dpa3[i]<<"\n";
    //     cout << "dpb="<<dpb[i]<<"\n";
    //     cout << "dpba="<<dpba[i]<<"\n";
    //     cout << "dpba2="<<dpba2[i]<<"\n";
    //     cout << "dpba3="<<dpba3[i]<<"\n";
    // }
    cout << dp0[N+1]/2;
}

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