Submission #868042

#	Time	Username	Problem	Language	Result	Execution time	Memory
868042		LittleOrange	Lamps (JOI19_lamps)	C++17	100 / 100	39 ms	51608 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
    ll l, r, t, sp=-1,m=0; // all0 all1 other
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    string a,b;
    cin >> n >> a >> b;
    vector<ll> dp0(n+1,1e18); // no
    vector<ll> dp1(n+1,1e18); // 0
    vector<ll> dp2(n+1,1e18); // 1
    vector<ll> dp3(n+1,1e18); // rev
    vector<ll> dp4(n+1,1e18); // 0+rev
    vector<ll> dp5(n+1,1e18); // 1+rev
    dp0[0] = 0;
    dp1[0] = dp2[0] = dp3[0] = 1;
    dp4[0] = dp5[0] = 2;
    for(ll i = 0;i<n;i++){
        if (a[i]==b[i]){
            dp0[i+1] = min(min(min(min(min(dp0[i],dp1[i]),dp2[i]),dp3[i]),dp4[i]),dp5[i]);
        }else{
            dp3[i+1] = min(min(min(dp0[i],dp1[i]),dp2[i])+1,min(min(dp3[i],dp4[i]),dp5[i]));
        }
        if (b[i] == '1'){
            dp2[i+1] = min(min(min(min(dp0[i],dp1[i]),dp3[i]),dp4[i])+1,min(dp2[i],dp5[i]));
            dp4[i+1] = min(min(min(dp0[i],dp2[i])+2,min(min(dp1[i],dp3[i]),dp5[i])+1),dp4[i]);
        }else{
            dp1[i+1] = min(min(min(min(dp0[i],dp2[i]),dp3[i]),dp5[i])+1,min(dp1[i],dp4[i]));
            dp5[i+1] = min(min(min(dp0[i],dp1[i])+2,min(min(dp2[i],dp3[i]),dp4[i])+1),dp5[i]);
        }
    }
    ll ans = min(min(min(min(min(dp0[n],dp1[n]),dp2[n]),dp3[n]),dp4[n]),dp5[n]);
    cout << ans << "\n";
}

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