Submission #1165019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165019		antonn	Lamps (JOI19_lamps)	C++20	0 / 100	5 ms	12132 KiB

lamp

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 1e6 + 7;

int dp[3][N], f[N], g[N], pref[N], noxor[N], suff[N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n; string a, b; cin >> n >> a >> b;
    a = "#" + a, b = "#" + b;
    f[0] = 2;
    for (int i = 1; i <= n; ++i) {
        char c;
        if (a[i] == b[i]) c = b[i] ^ '0' ^ '1';
        if (a[i] != b[i]) c = '?';
        if (c == '0') f[i] = 0;
        if (c == '1') f[i] = 1;
        if (c == '?') f[i] = 2;
        g[i] = b[i] - '0';
    }
    noxor[1] = 1;
    for (int i = 2; i <= n; ++i) noxor[i] = noxor[i - 1] + (g[i - 1] != g[i]);
    
    pref[1] = 1;
    for (int i = 2; i <= n; ++i) pref[i] = pref[i - 1] + (f[i - 1] != f[i]);
    
    for (int i = 0; i < 3; ++i) for (int j = 0; j < N; ++j) dp[i][j] = 1e9;
    dp[f[0]][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) { // xorez
            for (int x = 0; x < 3; ++x) {
                int cost = 0;
                cost += dp[x][j - 1]; 
                cost += 1 + pref[i] - pref[j];
                cost -= (f[j] == x);
                ckmin(dp[f[i]][i], cost + 1);
            }
        }
        for (int j = 1; j <= i; ++j) { // nu xorez
            for (int x = 0; x < 3; ++x) {
                int cost = 0;
                cost += dp[x][j - 1];
                cost += 1 + noxor[i] - noxor[j];
                cost -= (x == g[i]);
                ckmin(dp[g[i]][i], cost);
            }
        }
        if (a[i] == b[i]) {
            for (int x = 0; x < 3; ++x) ckmin(dp[2][i], dp[x][i - 1]);
        }
    }
    suff[n] = 1;
    for (int i = n - 1; i >= 1; --i) suff[i] = suff[i + 1] + (b[i] != b[i + 1]);
    int ans = 1e9;
    for (int i = 0; i <= n; ++i) for (int x = 0; x < 3; ++x) ckmin(ans, dp[x][i] + suff[i + 1]);
    for (int i = 0; i <= n; ++i) for (int x = 0; x < 3; ++x) if (dp[x][i] + suff[i + 1] == 2) cout << x << " " << i << "\n";
    cout << ans << "\n";
}
/**
13
1010010010100
0000111001011
0000111010100

**/

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