Submission #659924

#	Time	Username	Problem	Language	Result	Execution time	Memory
659924		cristi_a	Lamps (JOI19_lamps)	C++17	4 / 100	23 ms	19904 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6;
const int inf = 1e9;

int dp[nmax+5][4];
// 0 nimic
// 1 off
// 2 on
// 3 toggle

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; string a, b; cin >> n >> a >> b;
    a = " " + a; b = " " + b;
    for(int i=0; i<=n; i++)
        for(int j=0; j<=3; j++)
            dp[i][j] = inf;
    dp[0][0] = 0;
    for(int i=1; i<=n; i++) {
        if(a[i] == '0' and b[i] == '0') {
            dp[i][0] = min({dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3]});
            dp[i][1] = min({dp[i-1][0] + 1, dp[i-1][1], dp[i-1][2] + 1, dp[i-1][3] + 1});
        }
        else if(a[i] == '0' and b[i] == '1') {
            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][3] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2] + 1, dp[i-1][3]});
        }
        else if(a[i] == '1' and 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][3] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2] + 1, dp[i-1][3]});
        }
        else if(a[i] == '1' and b[i] == '1') {
            dp[i][0] = min({dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3]});
            dp[i][2] = min({dp[i-1][0] + 1, dp[i-1][1] + 1, dp[i-1][2], dp[i-1][3] + 1});
        }
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]});
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49