Submission #893919

#	Time	Username	Problem	Language	Result	Execution time	Memory
893919		box	Lamps (JOI19_lamps)	C++17	100 / 100	75 ms	4776 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    string A, B;
    cin >> A >> B;
    int dp[3][2], ndp[3][2];
    for (int x : {0,1,2}) for (int y : {0,1}) dp[x][y] = INF;
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int x : {0,1,2}) for (int y : {0,1}) ndp[x][y] = INF;
        for (int x1 : {0,1,2}) for (int y1 : {0,1}) for (int x2 : {0,1,2}) for (int y2 : {0,1})
            ndp[x2][y2] = min(ndp[x2][y2], dp[x1][y1] + (x1 != x2 && x2 > 0) + (y2 > y1));
        for (int x : {0,1,2}) for (int y : {0,1}) {
            int v = (x ? x - 1 : A[i] - '0') ^ y;
            if (v != B[i] - '0') ndp[x][y] = INF;
        }
        swap(dp, ndp);
    }
    int ans = INF;
    for (int x : {0,1,2}) for (int y : {0,1}) ans = min(ans, dp[x][y]);
    cout << ans << '\n';
}

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