Submission #1059260

#TimeUsernameProblemLanguageResultExecution timeMemory
1059260oscar1fLamps (JOI19_lamps)C++17
51 / 100
449 ms262144 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int TAILLE_MAX=1000*1000+5,INFINI=1000*1000*1000;
int taille;
char carac;
int init[TAILLE_MAX],obj[TAILLE_MAX];
int memo[TAILLE_MAX][2][3][2];

int calcTransi(int xorSous,int milieu,int xorSur,int nouvSous,int nouvMil,int nouvSur) {
    int ans=0;
    if (xorSous==0 and nouvSous==1) {
        ans++;
    }
    if (milieu!=nouvMil and nouvMil!=2) {
        ans++;
    }
    if (xorSur==0 and nouvSur==1) {
        ans++;
    }
    return ans;
}

int calcVal(int val,int xorSous,int milieu,int xorSur) {
    val^=xorSous;
    if (milieu!=2) {
        val=milieu;
    }
    val^=xorSur;
    return val;
}

int dyna(int pos,int xorSous,int milieu,int xorSur) {
    if (pos==taille) {
        return 0;
    }
    int ans=memo[pos][xorSous][milieu][xorSur];
    if (ans!=INFINI) {
        return ans;
    }
    int coutTransi;
    for (int j=0;j<2;j++) {
        for (int k=0;k<3;k++) {
            for (int l=0;l<2;l++) {
                if (milieu!=k or milieu==2) {
                    coutTransi=min(calcTransi(xorSous,milieu,xorSur,j,k,l),calcTransi(xorSur,milieu,xorSous,j,k,l));
                }
                else {
                    coutTransi=calcTransi(xorSous,milieu,xorSur,j,k,l);
                }
                if (calcVal(init[pos],j,k,l)==obj[pos]) {
                    ans=min(ans,coutTransi+dyna(pos+1,j,k,l));
                }
            }
        }
    }
    memo[pos][xorSous][milieu][xorSur]=ans;
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>taille;
    for (int i=0;i<taille;i++) {
        cin>>carac;
        if (carac=='1') {
            init[i]=1;
        }
    }
    for (int i=0;i<taille;i++) {
        cin>>carac;
        if (carac=='1') {
            obj[i]=1;
        }
    }
    for (int i=0;i<taille;i++) {
        for (int j=0;j<2;j++) {
            for (int k=0;k<3;k++) {
                for (int l=0;l<2;l++) {
                    memo[i][j][k][l]=INFINI;
                }
            }
        }
    }
    cout<<dyna(0,0,2,0)<<endl;
    return 0;
}
 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...