Submission #1185784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185784		irmuun	Lamps (JOI19_lamps)	C++20	100 / 100	35 ms	22024 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    int a[n+5],b[n+5];
    for(int i=1;i<=n;i++){
        a[i]=(s[i-1]-'0');
        b[i]=(t[i-1]-'0');
    }
    int dp[n+5][3];
    dp[0][0]=0;
    dp[0][1]=dp[0][2]=1e9;
    //dp[i][j]=x+y, x-set range, y-flip range
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++) dp[i][j]=1e9;
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                int bef=0;//1-same,0-dif
                int now=0;
                if(i==1) bef=1;
                else{
                    if(j==0) bef=(a[i-1]==b[i-1]?1:0);
                    else if(j==1) bef=(b[i-1]==0?1:0);
                    else bef=(b[i-1]==1?1:0);
                }
                if(k==0) now=(a[i]==b[i]?1:0);
                else if(k==1) now=(b[i]==0?1:0);
                else now=(b[i]==1?1:0);
                dp[i][k]=min(dp[i][k],dp[i-1][j]+(k!=0&&k!=j)+(bef==1&&now==0));
            }
        }
    }
    cout<<min({dp[n][0],dp[n][1],dp[n][2]});
}

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