Submission #1212564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212564		minhpk	Lamps (JOI19_lamps)	C++20	4 / 100	139 ms	158956 KiB

lamp

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

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]!=s[i]){
        res= min(res,dp(i+1,3));
    }else if (s1[i]!=s[i]){
        res= min(res,1+dp(i+1,3));
    }

    if (j==5 && s1[i]=='0'){
        res= min(res,dp(i+1,5));
    }else if (j==5 && s1[i]!='0'){
        res= min(res,(s1[i-1]=='0')+dp(i+1,5));
    }else{
        res= min(res,1+(s1[i]=='1')+dp(i+1,5));
    }


    if (j==6 && s1[i]=='1'){
        res= min(res,dp(i+1,6));
    }else if (j==6 && s1[i]!='1'){
        res= min(res,(s1[i-1]=='1')+dp(i+1,6));
    }else{
        res= min(res,1+(s1[i]=='0')+dp(i+1,6));
    }

    if (j==7 && s1[i]!=s[i]){
        res= min(res,dp(i+1,7));
    }else if (j==7 && s1[i]==s1[i]){
        res= min(res,(s1[i-1]!=s1[i])+dp(i+1,7));
    }else{
        res= min(res,1+(s1[i]==s[i])+dp(i+1,7));
    }

    return f[i][j]=res;
}

signed main()
{
  //  freopen("test.txt", "r", stdin);
   // freopen("o2.out", "w", stdout);
    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<=9;j++){
              f[i][j]=-1;
         }
    }
    cout << dp(1,0) << "\n";
  //  cout << f[2][5] << "\n";
    return 0;
}


/*
8
00100010
10000100
*/


/*
freopen("test.txt", "r", stdin);
    freopen("o2.out", "w", stdout);
*/

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