oj.uz

Submission #129195

# Submission time Handle Problem Language Result Execution time Memory
129195 2019-07-11T19:56:55 Z MohamedAhmed04 Lamps (JOI19_lamps) C++14
4 / 100
 259 ms 104404 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 ;
    if (t0 == 1 && t1 == 1)
      while (1) ;
    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(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;
                }
                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 ;
                }
                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 27 ms 31608 KB Output is correct
3 Correct 27 ms 31620 KB Output is correct
4 Correct 27 ms 31556 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 Correct 27 ms 31608 KB Output is correct
9 Correct 27 ms 31608 KB Output is correct
10 Correct 27 ms 31608 KB Output is correct
11 Correct 27 ms 31608 KB Output is correct
12 Correct 27 ms 31608 KB Output is correct
13 Correct 27 ms 31636 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 31620 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 27 ms 31608 KB Output is correct
3 Correct 27 ms 31620 KB Output is correct
4 Correct 27 ms 31556 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 Correct 27 ms 31608 KB Output is correct
9 Correct 27 ms 31608 KB Output is correct
10 Correct 27 ms 31608 KB Output is correct
11 Correct 27 ms 31608 KB Output is correct
12 Correct 27 ms 31608 KB Output is correct
13 Correct 27 ms 31636 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 31620 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 27 ms 31608 KB Output is correct
2 Correct 27 ms 31608 KB Output is correct
3 Correct 33 ms 31644 KB Output is correct
4 Correct 31 ms 31596 KB Output is correct
5 Correct 27 ms 31608 KB Output is correct
6 Correct 27 ms 31608 KB Output is correct
7 Correct 238 ms 104272 KB Output is correct
8 Correct 243 ms 104288 KB Output is correct
9 Correct 236 ms 104248 KB Output is correct
10 Correct 234 ms 104404 KB Output is correct
11 Correct 234 ms 104388 KB Output is correct
12 Correct 255 ms 104236 KB Output is correct
13 Correct 259 ms 104112 KB Output is correct
14 Correct 236 ms 104208 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 27 ms 31608 KB Output is correct
3 Correct 27 ms 31620 KB Output is correct
4 Correct 27 ms 31556 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 Correct 27 ms 31608 KB Output is correct
9 Correct 27 ms 31608 KB Output is correct
10 Correct 27 ms 31608 KB Output is correct
11 Correct 27 ms 31608 KB Output is correct
12 Correct 27 ms 31608 KB Output is correct
13 Correct 27 ms 31636 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 31620 KB Output isn't correct
17 Halted 0 ms 0 KB -