Submission #1212898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212898		minhpk	Lamps (JOI19_lamps)	C++20	0 / 100	215 ms	291884 KiB

lamp

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

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

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

    if (j==2 && s1[i]=='1'){
        res= min(res,dp(i+1,2,0));
    }else if (s1[i]=='1'){
        int add=1;
        if (j==7 && k==2){
            add=0;
        }
        res= min(res,add+dp(i+1,2,0));
    }

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

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


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

    if (j==7 && s1[i]!=s[i]){
        res= min(res,dp(i+1,7,k));
    }else if (j==7 && s1[i]==s[i]){
        int add=1;
        int t=0;
        if (k==1 && s1[i]=='0'){
            add=0;
        }
        if (k==2 && s1[i]=='1'){
            add=0;
        }
        if (s1[i]=='0'){
            t=1;
        }else{
            t=2;
        }
        res=min(res,add+dp(i+1,7,t));
    }else{
        res= min(res,1+dp(i+1,7,0));
    }


    return f[i][j][k]=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<=7;j++){
             for (int k=0;k<=2;k++){
                  f[i][j][k]=-1;
             }
         }
    }
    for (int i=a;i>=1;){
         if (s1[i]=='0'){
             int base=i;
             while (s1[i]=='0'){
                next0[i]=base;
                i--;
             }
         }else{
             i--;
         }

    }
    for (int i=a;i>=1;){
         if (s1[i]=='1'){
             int base=i;
             while (s1[i]=='1'){
                next1[i]=base;
                i--;
             }
         }else{
             i--;
         }

    }
    cout << dp(1,0,0) << "\n";
    return 0;
}


/*
8
01010101
10111000


8
01010101
10111000
10101010


6
110110
011101


001001


8
01010101
11000010

10101010

*/


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

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