oj.uz

Submission #129193

# Submission time Handle Problem Language Result Execution time Memory
129193 2019-07-11T19:51:40 Z MohamedAhmed04 Lamps (JOI19_lamps) C++14
0 / 100
 258 ms 119912 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e6 + 5 ;

int dp[MAX][2][2][2] ;

int arr[MAX] , arr2[MAX] ;

int n ;

int solve(int idx , int t , int t0 , int t1)
{
    if(idx == n)
        return 0 ;
    int &ret = dp[idx][t][t0][t1] ;
    if(ret != -1)
        return ret ;
    ret = 1e9 ;
    //debugging
    if(t0 && t1)
        while(1) ;
    if(t)
    {
        if(arr[idx] != arr2[idx])
        {
            if(t0 && arr2[idx] == 1)
                ret = solve(idx+1 , t , 0 , t1) ;
            else if(t1 && arr2[idx] == 0)
                ret = solve(idx+1 , t , t0 , 0) ;
            else
            {
                ret = solve(idx+1 , t , t0 , t1) ;
            }
            return ret ;
        }
        else
        {
            int choice1 = 1e9 , choice2 = 1e9 ;
            /*if(arr2[idx] == 0)
            {
                choice1 = solve(idx+1 , 0 , 1 , 0) + 1;
                choice2 = solve(idx+1 , 1 , 1 , 0) + 1;
                ret = min(choice1 , choice2) ;
                return ret ;
            }
            else
            {
                choice1 = solve(idx+1 , 0 , 0 , 1) + 1 ;
                choice2 = solve(idx+1 , 1 , 0 , 1) + 1 ;
                ret = min(choice1 , choice2) ;
                return ret ;
            }*/
            if(arr[idx] == 0)
            {
                if(t0 == 1)
                    choice1 = solve(idx+1 , t , t0 , t1) ;
                else
                {
                    choice1 = solve(idx+1 , 0 , 0 , 0) ;
                    choice2 = solve(idx+1 , 1 , 1 , 0) + 1;
                    choice2 = min(choice2 , solve(idx+1 , 0 , 1 , 0) + 1);
                }
                ret = min(choice1 , choice2) ;
                return ret ;
            }
            else
            {
                if(t1 == 1)
                    choice1 = solve(idx+1 , t , t0 , t1) ;
                else
                {
                    choice1 = solve(idx+1 , 0 , 0,  0) ;
                    choice2 = solve(idx+1 , 1 , 0 , 1) + 1 ;
                    choice2 = min(choice2 , solve(idx+1 , 0 , 0 , 1) + 1) ;
                }
                ret = min(choice1 , choice2) ;
                return ret ;
            }
        }
    }
    if(t1)
    {
        if(arr2[idx] == 1)
            ret = solve(idx+1 , t , t0 , t1) ;
        else
        {
            if(arr[idx] == arr2[idx])
                ret = solve(idx+1 , t , t0 , t1) ;
            else
            {
                int choice1 = solve(idx+1 , 1 , 0 , 0) + 1 ;
                int choice2 = solve(idx+1 , 0 , 1 , 0) + 1 ;
                //int choice3 = solve(idx+1 , 1 , 1 , 0) + 2 ;
                ret = min(choice1 , choice2) ;
            }
            return ret ;
        }
        return ret ;
    }
    if(t0)
    {
        if(arr2[idx] == 0)
            ret = solve(idx+1 , t , t0 , t1) ;
        else
        {
            if(arr[idx] == arr2[idx])
                ret = solve(idx+1 , 0 , 0 , 0) ;
            else
            {
                int choice1 = solve(idx+1 , 1 , 0 , 0) + 1 ;
                int choice2 = solve(idx+1 , 0 , 0 , 1) + 1 ;
                //int choice3 = solve(idx+1 , 1 , 1 , 0) + 2 ;
                ret = min(choice1 , choice2) ;
            }
            return ret ;
        }
        return ret ;
    }
    if(arr[idx] == arr2[idx])
        ret = solve(idx+1 , t , t0 , t1) ;
    else
    {
        int choice1 = solve(idx+1 , 1 , 0 , 0) + 1 ;
        int choice2 = 1e9 ;
        if(arr2[idx] == 0)
            choice2 = solve(idx+1 , 0 , 1 , 0) + 1 ;
        else
            choice2 = solve(idx+1 , 0 , 0 , 1) + 1 ;
        ret = min(choice1 , choice2) ;
    }
    return ret ;
}

int main()
{
    cin>>n ;
    string s1 , s2 ;
    cin>>s1>>s2 ;
    for(int i = 0 ; i < n ; ++i)
        arr[i] = (s1[i] - '0') ;
    for(int i = 0 ; i < n ; ++i)
        arr2[i] = (s2[i] - '0') ;
    memset(dp , -1 , sizeof(dp)) ;
    return cout<<solve(0 , 0 , 0 , 0)<<"\n" , 0 ;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31608 KB Output is correct
2 Correct 32 ms 31612 KB Output is correct
3 Correct 32 ms 31608 KB Output is correct
4 Correct 33 ms 31608 KB Output is correct
5 Correct 27 ms 31608 KB Output is correct
6 Correct 27 ms 31608 KB Output is correct
7 Correct 27 ms 31608 KB Output is correct
8 Incorrect 27 ms 31608 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31608 KB Output is correct
2 Correct 32 ms 31612 KB Output is correct
3 Correct 32 ms 31608 KB Output is correct
4 Correct 33 ms 31608 KB Output is correct
5 Correct 27 ms 31608 KB Output is correct
6 Correct 27 ms 31608 KB Output is correct
7 Correct 27 ms 31608 KB Output is correct
8 Incorrect 27 ms 31608 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31628 KB Output is correct
2 Correct 27 ms 31608 KB Output is correct
3 Correct 28 ms 31596 KB Output is correct
4 Correct 27 ms 31612 KB Output is correct
5 Correct 32 ms 31608 KB Output is correct
6 Correct 28 ms 31664 KB Output is correct
7 Correct 235 ms 119832 KB Output is correct
8 Incorrect 258 ms 119912 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31608 KB Output is correct
2 Correct 32 ms 31612 KB Output is correct
3 Correct 32 ms 31608 KB Output is correct
4 Correct 33 ms 31608 KB Output is correct
5 Correct 27 ms 31608 KB Output is correct
6 Correct 27 ms 31608 KB Output is correct
7 Correct 27 ms 31608 KB Output is correct
8 Incorrect 27 ms 31608 KB Output isn't correct
9 Halted 0 ms 0 KB -