oj.uz

Submission #129196

# Submission time Handle Problem Language Result Execution time Memory
129196 2019-07-11T20:01:20 Z MohamedAhmed04 Lamps (JOI19_lamps) C++14
4 / 100
 276 ms 120056 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 , 0 , 0 , 0) ;
            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 27 ms 31608 KB Output is correct
2 Correct 32 ms 31592 KB Output is correct
3 Correct 30 ms 31864 KB Output is correct
4 Correct 32 ms 31608 KB Output is correct
5 Correct 28 ms 31608 KB Output is correct
6 Correct 27 ms 31608 KB Output is correct
7 Correct 32 ms 31608 KB Output is correct
8 Correct 32 ms 31608 KB Output is correct
9 Correct 31 ms 31608 KB Output is correct
10 Correct 32 ms 31608 KB Output is correct
11 Correct 32 ms 31608 KB Output is correct
12 Correct 33 ms 31608 KB Output is correct
13 Correct 27 ms 31608 KB Output is correct
14 Correct 27 ms 31608 KB Output is correct
15 Correct 27 ms 31608 KB Output is correct
16 Incorrect 27 ms 31608 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 32 ms 31592 KB Output is correct
3 Correct 30 ms 31864 KB Output is correct
4 Correct 32 ms 31608 KB Output is correct
5 Correct 28 ms 31608 KB Output is correct
6 Correct 27 ms 31608 KB Output is correct
7 Correct 32 ms 31608 KB Output is correct
8 Correct 32 ms 31608 KB Output is correct
9 Correct 31 ms 31608 KB Output is correct
10 Correct 32 ms 31608 KB Output is correct
11 Correct 32 ms 31608 KB Output is correct
12 Correct 33 ms 31608 KB Output is correct
13 Correct 27 ms 31608 KB Output is correct
14 Correct 27 ms 31608 KB Output is correct
15 Correct 27 ms 31608 KB Output is correct
16 Incorrect 27 ms 31608 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31608 KB Output is correct
2 Correct 28 ms 31636 KB Output is correct
3 Correct 27 ms 31616 KB Output is correct
4 Correct 27 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 236 ms 119916 KB Output is correct
8 Correct 253 ms 119908 KB Output is correct
9 Correct 254 ms 119784 KB Output is correct
10 Correct 256 ms 120056 KB Output is correct
11 Correct 263 ms 119968 KB Output is correct
12 Correct 276 ms 119868 KB Output is correct
13 Correct 261 ms 119884 KB Output is correct
14 Correct 253 ms 119780 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31608 KB Output is correct
2 Correct 32 ms 31592 KB Output is correct
3 Correct 30 ms 31864 KB Output is correct
4 Correct 32 ms 31608 KB Output is correct
5 Correct 28 ms 31608 KB Output is correct
6 Correct 27 ms 31608 KB Output is correct
7 Correct 32 ms 31608 KB Output is correct
8 Correct 32 ms 31608 KB Output is correct
9 Correct 31 ms 31608 KB Output is correct
10 Correct 32 ms 31608 KB Output is correct
11 Correct 32 ms 31608 KB Output is correct
12 Correct 33 ms 31608 KB Output is correct
13 Correct 27 ms 31608 KB Output is correct
14 Correct 27 ms 31608 KB Output is correct
15 Correct 27 ms 31608 KB Output is correct
16 Incorrect 27 ms 31608 KB Output isn't correct
17 Halted 0 ms 0 KB -