Submission #1286935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286935		trinm01	Lamps (JOI19_lamps)	C++20	100 / 100	41 ms	18176 KiB

lamp

// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const int MAXN = 1e6 + 5;
const ll oo = 1e9 + 7;
const int base = 10;

int n;
string a, b;
int dp[MAXN][4];

bool match(int i, int j) {
    char c = (j == 2 ? a[i] : char('0' + j));
    return c == b[i];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if(!(cin >> n >> a >> b)) return 0;
    FOR(i, 0, n){
    	dp[i][0]=dp[i][1]=dp[i][2]=oo;
    }
    dp[0][2] = 0;

    FOR(i, 0, n-1){
        FOR(j, 0, 2){
            if(dp[i][j] == oo) continue;
            FOR(k, 0, 2){
                int cst = dp[i][j];
                cst += (j != k && k != 2) ? 1 : 0;
                bool chk = (i == 0) ? true : match(i-1, j);
                bool chk2 = match(i, k);
                cst += (chk && !chk2) ? 1 : 0;
                if(cst < dp[i+1][k]) dp[i+1][k] = cst;
            }
        }
    }

    int ans = min({dp[n][0], dp[n][1], dp[n][2]});
    cout << ans << '\n';
    return 0;
}

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