Submission #1212513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212513		minhpk	Lamps (JOI19_lamps)	C++20	4 / 100	81 ms	119792 KiB

lamp

#include <bits/stdc++.h>
#define int long long
using namespace std;
string s,s1;
int a;
int f[1000001][5];

int dp(int i,int j){
    if (i>a){
        return 0;
    }
    if (f[i][j]!=-1){
        return f[i][j];
    }
    f[i][j]=1e7;
    int res=1e7;
    if (j==1 && s1[i]=='0'){
        res= min(res,dp(i+1,1));
    }else if (s1[i]=='0'){
        res= min(res,1+dp(i+1,1));
    }

    if (s[i]==s1[i]){
        res= min(res,dp(i+1,0));
    }

    if (j==2 && s1[i]=='1'){
        res= min(res,dp(i+1,2));
    }else if (s1[i]=='1'){
        res= min(res,1+dp(i+1,2));
    }
    if (j==3 && s1[i]-'0'=='1'-s[i]){
        res= min(res,dp(i+1,3));
    }else if (s1[i]-'0'=='1'-s[i]){
        res= min(res,1+dp(i+1,3));
    }
    return f[i][j]=res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    cin >> s >> s1;
    s='#'+s;
    s1='#'+s1;
    for (int i=1;i<=a;i++){
         for (int j=0;j<=4;j++){
              f[i][j]=-1;
         }
    }
    cout << dp(1,0) << "\n";
    return 0;
}

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