oj.uz

Submission #866619

# Submission time Handle Problem Language Result Execution time Memory
866619 2023-10-26T14:14:02 Z lolismek Lamps (JOI19_lamps) C++14
4 / 100
 106 ms 28164 KB 
#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 1e6;
const int INF = 1e9;

int dp[NMAX + 1][6];

int Min(vector <int> v){
    int mini = INF;
    for(int x : v){
        mini = min(mini, x);
    }
    return mini;
}

int main(){

    int n;
    cin >> n;

    string a, b;
    cin >> a >> b;

    a = "$" + a, b = "$" + b;

    for(int i = 0; i <= n; i++){
        for(int j = 0; j < 6; j++){
            dp[i][j] = INF;
            dp[i][j] = INF;
        }
    }

    dp[0][0] = 0;

    for(int i = 1; i <= n; i++){
        if(a[i] == b[i]){
            dp[i][0] = Min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2], dp[i - 1][3], dp[i - 1][4], dp[i - 1][5]});
        }else{
            dp[i][3] = Min({dp[i - 1][0] + 1, dp[i - 1][1] + 1, dp[i - 1][2] + 1, dp[i][3], dp[i][4], dp[i][5]});
        }

        if(b[i] == '0'){
            dp[i][1] = Min({dp[i - 1][0] + 1, dp[i - 1][1], dp[i - 1][2] + 1, dp[i - 1][3] + 1, dp[i - 1][4], dp[i - 1][5] + 1});
            dp[i][5] = Min({dp[i - 1][0] + 2, dp[i - 1][1] + 2, dp[i - 1][2] + 1, dp[i - 1][3] + 1, dp[i - 1][4] + 1, dp[i - 1][5]});
        }else{
            dp[i][2] = Min({dp[i - 1][0] + 1, dp[i - 1][1] + 1, dp[i - 1][2], dp[i - 1][3] + 1, dp[i - 1][4] + 1, dp[i - 1][5]});
            dp[i][4] = Min({dp[i - 1][0] + 2, dp[i - 1][1] + 1, dp[i - 1][2] + 2, dp[i - 1][3] + 1, dp[i - 1][4], dp[i - 1][5] + 1});
        }
    }

    cout << Min({dp[n][0], dp[n][1], dp[n][2], dp[n][3], dp[n][4], dp[n][5]});

    return 0;
}

/*
Notice how op1 & op2 dont overlap, how op3 does not overlap, how op3 comes on top.

0 - nothing
1 - op 1
2 - op 2
3 - op 3
4 - op1 & op3
5 - op2 & op3
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 452 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 106 ms 27876 KB Output is correct
8 Correct 95 ms 27804 KB Output is correct
9 Correct 98 ms 28164 KB Output is correct
10 Correct 94 ms 27812 KB Output is correct
11 Correct 95 ms 27800 KB Output is correct
12 Correct 101 ms 27712 KB Output is correct
13 Correct 101 ms 27804 KB Output is correct
14 Correct 98 ms 27880 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -