Submission #1067198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067198		Braabebo10	Lamps (JOI19_lamps)	C++14	100 / 100	60 ms	51472 KiB

lamp

#include <bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
int main() {
    fast
    ll n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    ll dp[n+10][3][2];
    memset(dp,0x3f, sizeof(dp));
    dp[n][0][0]=0;
    for(ll i=n-1;i>=0;i--){
        for(ll j=0;j<3;j++){
            for(ll k=0;k<2;k++){
                ll val=a[i]-'0';
                if(j==1)val=0;
                if(j==2)val=1;
                if(k==1)val^=1;
                if(val!=(b[i]-'0'))continue;
                for(ll j2=0;j2<3;j2++){
                    for(ll k2=0;k2<2;k2++){
                        dp[i][j][k]=min(dp[i][j][k],dp[i+1][j2][k2]+(j>0&&j!=j2)+(k>0&&k2!=k));
                    }
                }
            }
        }
    }
    ll ans=1e18;
    for(ll j=0;j<3;j++)
        for(ll k=0;k<2;k++)ans=min(ans,dp[0][j][k]);
    cout<<ans;
    return 0;
}

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