Submission #1064236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064236		ThylOne	Lamps (JOI19_lamps)	C++14	0 / 100	116 ms	262144 KiB

lamp

//####################
//Lamps
//####################
#include<bits/stdc++.h>

using namespace std;
string A,B;
const int inf = 2*1e6;
bool apply(bool a,int m){
    if(m==1)return 0;
    if(m==2)return 1;
    if(m==3)return !a;
    return a;
}
int dp[(int)1e6][4][4][4];
int solve(int pos, int s1=0,int s2=0,int s3=0){
    
    if(pos==A.size())return 0;
    if(dp[pos][s1][s2][s3]!=-1)return dp[pos][s1][s2][s3];
    int re = inf;
    for(int a=0;a<4;a++)
        for(int b=0;b<4;b++)
            for(int c=0;c<4;c++){
                //les cas impossibles
                if(a==0 && (b || c))continue;
                if(b==0 && c)continue;
                if((a==b && a!=0) || (b==c && b!=0) || (a==c && a!=0))continue;
                

                int cost = (bool)a+(bool)b+bool(c);
                if(a==s1){
                    cost-=(bool)a;
                    if(b==s2){
                        cost-=(bool)b;
                        if(c==s3)
                            cost-=(bool)c;
                    }
                }
                
                bool r = (A[pos]-'0');
                r = apply(r,a);
                r = apply(r,b);
                r = apply(r,c);
                if(r==(bool)(B[pos]-'0')){
                    re = min(re, cost+solve(pos+1,a,b,c));
                }
            }
    return dp[pos][s1][s2][s3]=re;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    int n; cin >> n;
    cin >> A >> B;
    for(int i = 0;i<1e6;i++){
         for(int a=0;a<4;a++)
        for(int b=0;b<4;b++)
            for(int c=0;c<4;c++)
                dp[i][a][b][c] = -1;
    }
    cout<<solve(0,0,0,0)<<endl;
    return 0;
};

Compilation message (stderr)

lamp.cpp: In function 'int solve(int, int, int, int)':
lamp.cpp:18:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if(pos==A.size())return 0;
      |        ~~~^~~~~~~~~~

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