Submission #483171

#	Time	Username	Problem	Language	Result	Execution time	Memory
483171		phamhoanghiep	Lamps (JOI19_lamps)	C++17	4 / 100	77 ms	30936 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+6;
string st;
string en;
int mask[maxn]; // 0: 0, 1: 1, 2: f, 3: 0f, 4: 1f, 5: nothing
int dp[maxn][6];
int n;
signed main() {
    cin>>n;
    cin>>st>>en;
    st=' '+st;
    en=' '+en;
    for(int i=1 ; i<=n ; i++) {
        if(st[i]!=en[i]) mask[i]+=(1<<2);
        if(en[i]=='0') mask[i]+=(1<<4)+(1<<0);
        if(en[i]=='1') mask[i]+=(1<<1)+(1<<3);
        dp[i][0]=dp[i][1]=dp[i][2]=dp[i][3]=dp[i][4]=dp[i][5]=n+1;
    }
    dp[0][0]=dp[0][1]=dp[0][2]=1; dp[0][3]=dp[0][4]=2; dp[0][5]=0;
    for(int i=1 ; i<=n ; i++) {
        if(en[i]=='0') {
            // 0 or 1f
            dp[i][0]=min({dp[i-1][0],dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3],dp[i-1][4]+1,dp[i-1][5]+1});
            dp[i][3]=min({dp[i-1][0]+1,dp[i-1][1]+2,dp[i-1][2]+1,dp[i-1][3],dp[i-1][4]+1,dp[i-1][5]+2});
        }
        else {
            dp[i][1]=min({dp[i-1][0]+1,dp[i-1][1],dp[i-1][2]+1,dp[i-1][3]+1,dp[i-1][4],dp[i-1][5]+1});
            dp[i][4]=min({dp[i-1][0]+2,dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3]+1,dp[i-1][4],dp[i-1][5]+2});
        }
        if(en[i]!=st[i]) {
            dp[i][2]=min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2],dp[i-1][3],dp[i-1][4],dp[i-1][5]+1});
        }
        else dp[i][5]=min({dp[i-1][0],dp[i-1][1],dp[i-1][2],dp[i-1][3],dp[i-1][4],dp[i-1][5]});
    }
    cout<<min({dp[n][0],dp[n][1],dp[n][2],dp[n][3],dp[n][4],dp[n][5]});
}

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