Submission #879423

#	Time	Username	Problem	Language	Result	Execution time	Memory
879423		vjudge1	Lamps (JOI19_lamps)	C++17	100 / 100	213 ms	153340 KiB

lamp

// https://oj.uz/problem/view/JOI19_lamps

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

enum {
        Z = 0,
        O = 1,
        ZO = 2,
        OZ = 3,
        N = 4,
        ON = 1,
        OFF = 0
};

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        int n;
        string a, b;
        cin >> n >> a >> b;
        const int inf = 1e9 + 7;
        vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(2, vector<int>(5, inf)));
        f[0][0][N] = 0;

        // flip last

        for (int i = 0; i < n; i++) {
                for (int j = 0; j < 2; j++) {
                        for (int jj = 0; jj < 5; jj++) {
                                if (f[i][j][jj] == inf) continue;
                        }
                        for (int jj = 0; jj < 2; jj++) {
                                if ((0 ^ jj) == b[i] - '0') {
                                        f[i + 1][jj][Z] = min({f[i + 1][jj][Z],
                                                               f[i][j][Z],
                                                               f[i][j][OZ],
                                                               f[i][j][N] + 1,
                                                               f[i][j][O] + 1,
                                                               f[i][j][ZO]}) +
                                                          (j < jj);
                                        f[i + 1][jj][ZO] = min({f[i + 1][jj][ZO],
                                                                f[i][j][Z] + 1,
                                                                f[i][j][OZ] + 1,
                                                                f[i][j][N] + 2,
                                                                f[i][j][O] + 1,
                                                                f[i][j][ZO]}) +
                                                           (j < jj);
                                }
                                if ((1 ^ jj) == b[i] - '0') {
                                        f[i + 1][jj][O] = min({f[i + 1][jj][O],
                                                               f[i][j][Z] + 1,
                                                               f[i][j][OZ],
                                                               f[i][j][N] + 1,
                                                               f[i][j][O],
                                                               f[i][j][ZO]}) +
                                                          (j < jj);
                                        f[i + 1][jj][OZ] = min({f[i + 1][jj][OZ],
                                                                f[i][j][Z] + 1,
                                                                f[i][j][OZ],
                                                                f[i][j][N] + 2,
                                                                f[i][j][O] + 1,
                                                                f[i][j][ZO] + 1}) +
                                                           (j < jj);
                                }
                                if ((a[i] ^ jj) == b[i]) {
                                        f[i + 1][jj][N] = min({f[i + 1][jj][N],
                                                               f[i][j][N],
                                                               f[i][j][O],
                                                               f[i][j][Z],
                                                               f[i][j][OZ],
                                                               f[i][j][ZO]}) +
                                                          (j < jj);
                                }
                        }
                }
        }

        int res = inf;
        for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 5; j++) {
                        res = min(res, f[n][i][j]);
                }
        }
        cout << res;
}

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