Submission #153052

#	Time	Username	Problem	Language	Result	Execution time	Memory
153052		fedoseevtimofey	Lamps (JOI19_lamps)	C++14	100 / 100	358 ms	41608 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e6 + 7;

int dp[N][2][2][2];
int a[N], b[N];

const int Inf = 1e9 + 7;

bool valid(int i, int j, int k, int id) {
    if (i == 1 && j == 1) return false;
    int x = a[id];
    if (i) x = 0;
    if (j) x = 1;
    if (k) x ^= 1;
    return x == b[id];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        a[i] = c - '0';
    }
    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        b[i] = c - '0';
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                for (int t = 0; t < 2; ++t) {
                    dp[i][j][k][t] = Inf;
                }
            }
        }
    }
    dp[0][0][0][0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                for (int t = 0; t < 2; ++t) {
                    for (int nj = 0; nj < 2; ++nj) {
                        for (int nk = 0; nk < 2; ++nk) {
                            for (int nt = 0; nt < 2; ++nt) {
                                if (valid(nj, nk, nt, i)) {
                                    int delta = (nj > j) + (nk > k) + (nt > t);
                                    dp[i + 1][nj][nk][nt] = min(dp[i + 1][nj][nk][nt], dp[i][j][k][t] + delta);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = Inf;
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) ans = min(ans, dp[n][i][j][k]);
    cout << ans << '\n';
}

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