oj.uz

Submission #239063

# Submission time Handle Problem Language Result Execution time Memory
239063 2020-06-14T09:36:43 Z Dremix10 Lamps (JOI19_lamps) C++17
0 / 100
 5 ms 384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Incorrect 4 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Incorrect 4 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Incorrect 4 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Incorrect 4 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -