Submission #1268695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268695		khfares	Lamps (JOI19_lamps)	C++20	4 / 100	59 ms	57056 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll  = long long;
using pll = pair<ll, ll>;
void solve() {
    ll n; cin >> n;
    string a, b; cin >> a >> b;
    vector<vector<ll>> dp(n, vector<ll>(3, 1e18));
    dp[0][0] = ((a[0] == b[0]) ? 0 : 1);
    dp[0][1] = ((0 == b[0]) ? 1 : 2);
    dp[0][2] = ((1 == b[0]) ? 1 : 2);

    for (ll i = 1; i < n; i++) {
        for (ll prev = 0; prev < 3; prev++) {
            char xprev = ((prev == 0) ? a[i-1] : ((prev == 1) ? '0' : '1'));
            bool dprev = (xprev != b[i-1]);
            for (ll cur = 0; cur < 3; cur++) {
                char x = ((cur == 0) ? a[i] : ((cur == 1) ? '0' : '1'));
                ll cost;
                if (cur == 0) cost = 0;
                else if (cur == 1) cost = (prev == 1 ? 0 : 1);
                else  cost = (prev == 2 ? 0 : 1);
                bool d = (x != b[i]);
                dp[i][cur] = min(dp[i][cur], dp[i-1][prev]+cost+((d && !dprev) ? 1 : 0));
            }
        }
    }
    cout << min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2])) << endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //___________________________
    solve();
    return 0;
}

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