Submission #1059266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059266		oscar1f	Lamps (JOI19_lamps)	C++17	100 / 100	496 ms	18256 KiB

lamp

#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[2][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 j=0;j<2;j++) {
        for (int k=0;k<3;k++) {
            for (int l=0;l<2;l++) {
                memo[taille%2][j][k][l]=0;
            }
        }
    }
    int ans,coutTransi;
    for (int pos=taille-1;pos>=0;pos--) {
        for (int xorSous=0;xorSous<2;xorSous++) {
            for (int milieu=0;milieu<3;milieu++) {
                for (int xorSur=0;xorSur<2;xorSur++) {
                    ans=INFINI;
                    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+memo[(pos+1)%2][j][k][l]);
                                }
                            }
                        }
                    }
                    memo[pos%2][xorSous][milieu][xorSur]=ans;
                }
            }
        }
    }
    cout<<memo[0][0][2][0]<<endl;
    return 0;
}
 

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