Submission #866624

#	Time	Username	Problem	Language	Result	Execution time	Memory
866624		lolismek	Lamps (JOI19_lamps)	C++14	100 / 100	131 ms	27960 KiB

lamp

#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[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 - 1][3], dp[i - 1][4], dp[i - 1][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: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49