Submission #1212894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212894		minhpk	Lamps (JOI19_lamps)	C++20	10 / 100	138 ms	174576 KiB

lamp

#include <bits/stdc++.h>
#define int long long
using namespace std;
string s,s1;
int a;
int f[1000001][8];
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]){
        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));
    }

    if (j==5 && s1[i]=='0'){
        res= min(res,dp(i+1,5));
    }else if (j==5 && s1[i]!='0'){
        res= min(res,1+dp(next1[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,1+dp(next0[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]==s[i]){
        if (s1[i]=='0'){
            res=min(res,1+dp(next0[i]+1,7));
        }else{
            res=min(res,1+dp(next1[i]+1,7));
        }
    }else{
        res= min(res,1+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<=7;j++){
              f[i][j]=-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) << "\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: 6 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49