Submission #261047

#	Time	Username	Problem	Language	Result	Execution time	Memory
261047		keko37	Lamps (JOI19_lamps)	C++14	0 / 100	6 ms	4508 KiB

lamp

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1000005;

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

int nula (int lo, int hi) {
    int res = 0;
    for (int i = lo + 1; i <= hi; i++) {
        if (b[i] == '1' && b[i - 1] == '0') res++;
    }
    if (b[hi] == '0') res++;
    return res;
}

int jen (int lo, int hi) {
    int res = 0;
    for (int i = lo + 1; i <= hi; i++) {
        if (b[i] == '0' && b[i - 1] == '1') res++;
    }
    if (b[hi] == '1') res++;
    return res;
}

int raz (int lo, int hi) {
    int res = 0;
    for (int i = lo + 1; i <= hi; i++) {
        if (a[i] == b[i] && a[i - 1] != b[i - 1]) res++;
    }
    if (a[hi] != b[hi]) res++;
    return res;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    if (n > 18) return 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1e9;
        for (int j = i; j >= 0; j--) {
            int ost = (j == 0 ? 0 : dp[j - 1]);
            dp[i] = min(dp[i], ost + raz(j, i));
            dp[i] = min(dp[i], ost + 1 + jen(j, i));
            dp[i] = min(dp[i], ost + 1 + nula(j, i));
        }
    }
    cout << dp[n - 1];
    return 0;
}

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