oj.uz

Submission #129176

# Submission time Handle Problem Language Result Execution time Memory
129176 2019-07-11T19:15:00 Z MohamedAhmed04 Lamps (JOI19_lamps) C++14
4 / 100
 261 ms 106208 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 ;
    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(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 28 ms 31608 KB Output is correct
2 Correct 28 ms 31608 KB Output is correct
3 Correct 28 ms 31612 KB Output is correct
4 Correct 28 ms 31608 KB Output is correct
5 Correct 28 ms 31608 KB Output is correct
6 Correct 28 ms 31608 KB Output is correct
7 Correct 28 ms 31608 KB Output is correct
8 Correct 28 ms 31608 KB Output is correct
9 Correct 28 ms 31608 KB Output is correct
10 Correct 28 ms 31612 KB Output is correct
11 Correct 28 ms 31608 KB Output is correct
12 Correct 28 ms 31608 KB Output is correct
13 Incorrect 28 ms 31580 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31608 KB Output is correct
2 Correct 28 ms 31608 KB Output is correct
3 Correct 28 ms 31612 KB Output is correct
4 Correct 28 ms 31608 KB Output is correct
5 Correct 28 ms 31608 KB Output is correct
6 Correct 28 ms 31608 KB Output is correct
7 Correct 28 ms 31608 KB Output is correct
8 Correct 28 ms 31608 KB Output is correct
9 Correct 28 ms 31608 KB Output is correct
10 Correct 28 ms 31612 KB Output is correct
11 Correct 28 ms 31608 KB Output is correct
12 Correct 28 ms 31608 KB Output is correct
13 Incorrect 28 ms 31580 KB Output isn't correct
14 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 31608 KB Output is correct
3 Correct 28 ms 31652 KB Output is correct
4 Correct 27 ms 31648 KB Output is correct
5 Correct 28 ms 31608 KB Output is correct
6 Correct 28 ms 31736 KB Output is correct
7 Correct 224 ms 106084 KB Output is correct
8 Correct 261 ms 106160 KB Output is correct
9 Correct 241 ms 106056 KB Output is correct
10 Correct 239 ms 106208 KB Output is correct
11 Correct 239 ms 106184 KB Output is correct
12 Correct 256 ms 106084 KB Output is correct
13 Correct 256 ms 106064 KB Output is correct
14 Correct 244 ms 106084 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31608 KB Output is correct
2 Correct 28 ms 31608 KB Output is correct
3 Correct 28 ms 31612 KB Output is correct
4 Correct 28 ms 31608 KB Output is correct
5 Correct 28 ms 31608 KB Output is correct
6 Correct 28 ms 31608 KB Output is correct
7 Correct 28 ms 31608 KB Output is correct
8 Correct 28 ms 31608 KB Output is correct
9 Correct 28 ms 31608 KB Output is correct
10 Correct 28 ms 31612 KB Output is correct
11 Correct 28 ms 31608 KB Output is correct
12 Correct 28 ms 31608 KB Output is correct
13 Incorrect 28 ms 31580 KB Output isn't correct
14 Halted 0 ms 0 KB -