Submission #1350092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350092		Newtonabc	Lamps (JOI19_lamps)	C++20	100 / 100	66 ms	25944 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int dp[N][3][2];
int main(){
    int n; cin>>n;
    string a,b; cin>>a >>b;
    a=" "+a,b=" "+b;
    for(int i=0;i<=n;i++) for(int j=0;j<3;j++) for(int k=0;k<2;k++) dp[i][j][k]=n;
    dp[0][0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<2;k++){
                int st;
                if(j==0) st=a[i]-'0';
                else st=j-1;
                //cout<<i <<" " <<j <<" " <<k <<" ";
                st^=k;
                //cout<<st <<" ";
                if(st!=b[i]-'0'){
                    //cout<<"\n";
                    continue;
                }
                for(int pj=0;pj<3;pj++){
                    for(int pk=0;pk<2;pk++){
                        int dif=0;
                        if(pj!=j && j!=0) dif++;
                        if(pk!=k && k!=0) dif++;
                        dp[i][j][k]=min(dp[i][j][k],dp[i-1][pj][pk]+dif);
                    }
                }
                //cout<<dp[i][j][k] <<"\n";
            }
        }
    }
    int ans=n;
    for(int i=0;i<3;i++) for(int j=0;j<2;j++) ans=min(ans,dp[n][i][j]);
    cout<<ans;
}

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