Submission #943315

#	Time	Username	Problem	Language	Result	Execution time	Memory
943315		relex	Lamps (JOI19_lamps)	C++17	100 / 100	84 ms	35808 KiB

lamp

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ld = long double;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
gp_hash_table<ll, ll, custom_hash> app;
//const int MOD = 998244353;
//const int MOD = 1e9 + 7;

constexpr ll INF = 1e9;

vector<ll> a;


ll n, m, k, q, x, y, z, w, h, T;
string s, t;
double p;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    T = 1;
    //cin >> T;
    while (T--) {    
        cin >> n;
        cin >> s >> t;

        int a[n], b[n];
        for (int i = 0; i < n; i++) {
            a[i] = s[i] - '0';
            b[i] = t[i] - '0';
        }

        int dp[n + 1][3][2] = {}; // dp[index][setNumber (2 if don't change)][toggle]. Notice that toggle always comes after number
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 2; k++) {
                    dp[i][j][k] = INF;
                }
            }
        }

        int changetoggle[2][2] = {}; 
        changetoggle[0][1] = 1;

        int changenumber[3][3] = {};
        changenumber[0][1] = 1; changenumber[1][0] = 1; changenumber[2][0] = 1; changenumber[2][1] = 1;

        dp[0][2][0] = 0;


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 2; k++) {
                    for (int jj = 0; jj < 3; jj++) {
                        for (int kk = 0; kk < 2; kk++) {
                            int num = a[i];
                            if (jj != 2) num = jj;
                            if (kk) num = 1 - num;
                            if (num != b[i]) continue;
                            dp[i + 1][jj][kk] = min(dp[i + 1][jj][kk], dp[i][j][k] + changenumber[j][jj] + changetoggle[k][kk]);
                        }
                    }
                }
            }
        }

        int ans = INF;
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 2; k++) {
                ans = min(ans, dp[n][j][k]);
            }
        }
        printf("%i\n", ans);

        
    }


}

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