oj.uz

답안 #129185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129185 2019-07-11T19:37:05 Z MohamedAhmed04 Lamps (JOI19_lamps) C++14
4 / 100
 285 ms 104296 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(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

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 31608 KB Output is correct
2 Correct 28 ms 31608 KB Output is correct
3 Correct 31 ms 31608 KB Output is correct
4 Correct 27 ms 31608 KB Output is correct
5 Correct 28 ms 31608 KB Output is correct
6 Correct 27 ms 31736 KB Output is correct
7 Correct 28 ms 31608 KB Output is correct
8 Correct 27 ms 31608 KB Output is correct
9 Correct 27 ms 31612 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 31608 KB Output is correct
14 Correct 27 ms 31608 KB Output is correct
15 Correct 28 ms 31608 KB Output is correct
16 Incorrect 28 ms 31608 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 31608 KB Output is correct
2 Correct 28 ms 31608 KB Output is correct
3 Correct 31 ms 31608 KB Output is correct
4 Correct 27 ms 31608 KB Output is correct
5 Correct 28 ms 31608 KB Output is correct
6 Correct 27 ms 31736 KB Output is correct
7 Correct 28 ms 31608 KB Output is correct
8 Correct 27 ms 31608 KB Output is correct
9 Correct 27 ms 31612 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 31608 KB Output is correct
14 Correct 27 ms 31608 KB Output is correct
15 Correct 28 ms 31608 KB Output is correct
16 Incorrect 28 ms 31608 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 31612 KB Output is correct
2 Correct 32 ms 31608 KB Output is correct
3 Correct 27 ms 31580 KB Output is correct
4 Correct 27 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 222 ms 104268 KB Output is correct
8 Correct 238 ms 104164 KB Output is correct
9 Correct 233 ms 104292 KB Output is correct
10 Correct 234 ms 104164 KB Output is correct
11 Correct 235 ms 104232 KB Output is correct
12 Correct 285 ms 104180 KB Output is correct
13 Correct 235 ms 104164 KB Output is correct
14 Correct 243 ms 104296 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 31608 KB Output is correct
2 Correct 28 ms 31608 KB Output is correct
3 Correct 31 ms 31608 KB Output is correct
4 Correct 27 ms 31608 KB Output is correct
5 Correct 28 ms 31608 KB Output is correct
6 Correct 27 ms 31736 KB Output is correct
7 Correct 28 ms 31608 KB Output is correct
8 Correct 27 ms 31608 KB Output is correct
9 Correct 27 ms 31612 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 31608 KB Output is correct
14 Correct 27 ms 31608 KB Output is correct
15 Correct 28 ms 31608 KB Output is correct
16 Incorrect 28 ms 31608 KB Output isn't correct
17 Halted 0 ms 0 KB -