Submission #596740

#	Time	Username	Problem	Language	Result	Execution time	Memory
596740		czhang2718	Lamps (JOI19_lamps)	C++17	100 / 100	61 ms	24100 KiB

lamp

#include "bits/stdc++.h"
using namespace std;

const int N=1e6;
int n;
string s, t;
int a[N], b[N];
int dp[N][3];

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> s >> t;
    for(int i=0; i<n; i++){
        a[i]=s[i]=='1';
        b[i]=t[i]=='1';
        for(int j=0; j<3; j++) dp[i][j]=1e9;
    }

    dp[0][0]=1+b[0];
    dp[0][1]=1+!b[0];
    dp[0][2]=a[0]^b[0];
    // for(int k=0; k<3; k++) cout << dp[0][k] << " ";
    //         cout << "\n";
    for(int i=1; i<n; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<3; k++){
                int old=(j<2?j:a[i-1]);
                int val=(k<2?k:a[i]);
                dp[i][k]=min(dp[i][k], dp[i-1][j]+(j!=1 && k==1) + (j!=0 && k==0) + ((val^b[i])&&(old==b[i-1])));
            }
        }
        // for(int k=0; k<3; k++) cout << dp[i][k] << " ";
        //     cout << "\n";
    }

    cout << min({dp[n-1][0], dp[n-1][1], dp[n-1][2]});
}

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