Submission #239063

#	Time	Username	Problem	Language	Result	Execution time	Memory
239063		Dremix10	Lamps (JOI19_lamps)	C++17	0 / 100	5 ms	384 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
#define N (int)(1e6+1)

string a,b;
int n;
int dp[N][6];
bool v[N][6];

/// operation 0 -> no operation
/// operation 1 -> set 1
/// operation 2 -> set 0
/// operation 3 -> toggled
/// operation 4 -> set 1 and toggled
/// operation 5 -> set 0 and toggled

int solve(int x, int state){
    if(x==0)
        return 0;
    if(v[x][state])
        return dp[x][state];

    v[x][state]=1;
    int ans=mod;

    if(state==0){
        if(a[x-1]==b[x-1])
            ans=min(ans,solve(x-1,0));
        else
            ans=min(ans,solve(x-1,3)+1);

        if(b[x-1]=='1'){
            ans=min(ans,solve(x-1,1)+1);
            ans=min(ans,solve(x-1,5)+2);
        }
        else{
            ans=min(ans,solve(x-1,2)+1);
            ans=min(ans,solve(x-1,4)+2);
        }
    }

    else if(state==1){
         if(b[x-1]=='1'){
            ans=min(ans,solve(x-1,0));
            ans=min(ans,solve(x-1,1));
        }
        else
            ans=min(ans,solve(x-1,4)+1);

    }

    else if(state==2){
        if(b[x-1]=='1')
            ans=min(ans,solve(x-1,5)+1);

        else{
            ans=min(ans,solve(x-1,0));
            ans=min(ans,solve(x-1,2));
        }
    }

    else if(state==3){
        if(a[x-1]!=b[x-1]){
            ans=min(ans,solve(x-1,0));
            ans=min(ans,solve(x-1,3));
        }
    }

    else if(state==4){
        if(b[x-1]=='0'){
            ans=min(ans,solve(x-1,4));
            ans=min(ans,solve(x-1,0));
            ans=min(ans,solve(x-1,1));
        }
    }
    else{
        if(b[x-1]=='1'){
            ans=min(ans,solve(x-1,5));
            ans=min(ans,solve(x-1,0));
            ans=min(ans,solve(x-1,2));
        }
    }
    dp[x][state]=ans;
    return ans;
}

int main (){
fastio;

cin>>n;

cin>>a>>b;
int i,j;
for(i=1;i<=n;i++)
    for(j=0;j<6;j++)
        dp[i][j]=-1;
cout<<solve(n,0)<<endl;

}

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