Submission #797843

#	Time	Username	Problem	Language	Result	Execution time	Memory
797843		PurpleCrayon	Lamps (JOI19_lamps)	C++17	100 / 100	102 ms	4416 KiB

lamp

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 6e1+10, MOD = 1e9+7;
const ll INF = 1e18+10;

// 0 = empty
// 1 = {0}
// 2 = {1}
// 3 = {0, 1}
// 4 = {1, 0}

pair<int, int> trans(int prv, int nxt, int state) {
    if (prv == nxt) {
        if (nxt == 0) {
            if (state == 0) return {0, state};
            else if (state == 1) return {0, state};
            else if (state == 2) return {0, 0};
            else if (state == 3) return {0, 1};
            else if (state == 4) return {0, state};
        } else {
            if (state == 0) return {0, state};
            else if (state == 1) return {0, 0};
            else if (state == 2) return {0, state};
            else if (state == 3) return {0, state};
            else if (state == 4) return {0, 2};
        }
    }

    if (nxt == 1) { 
        if (state == 0) return {1, 2};
        else if (state == 1) return {1, 3};
        else if (state == 2) return {0, state};
        else if (state == 3) return {0, state};
        else if (state == 4) return {0, 2};
    } else {
        if (state == 0) return {1, 1};
        else if (state == 1) return {0, state};
        else if (state == 2) return {1, 4};
        else if (state == 3) return {0, 1};
        else if (state == 4) return {0, state};
    }

    assert(false);
}

int prv[5][2], cur[5][2];
void solve() {
    int n; cin >> n;
    string s, t; cin >> s >> t;

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 2; j++) {
            prv[i][j] = cur[i][j] = MOD;
        }
    }

    prv[0][0] = 0;
    for (int i = 0; i < n; i++) {
        int x = s[i] - '0', y = t[i] - '0';
        for (int prv_state = 0; prv_state < 5; prv_state++) {
            for (int prv_flip = 0; prv_flip < 2; prv_flip++) {
                for (int me = 0; me < 2; me++) {
                    int flip = me ^ y;
                    auto [cost, nxt_state] = trans(x, me, prv_state);
                    cost += flip && !prv_flip;

                    cur[nxt_state][flip] = min(cur[nxt_state][flip], prv[prv_state][prv_flip] + cost);
                }
            }
        }

        for (int j = 0; j < 5; j++) {
            for (int k = 0; k < 2; k++) {
                prv[j][k] = cur[j][k], cur[j][k] = MOD;
            }
        }
    }

    int ans = MOD;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 2; j++)
            ans = min(ans, prv[i][j]);

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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