Submission #511454

#	Time	Username	Problem	Language	Result	Execution time	Memory
511454		couplefire	Lamps (JOI19_lamps)	C++17	100 / 100	147 ms	122004 KiB

lamp

#include<bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 1000005;
 
int n, sol = 1e9;
string a, b;
int dp[MAXN][3][2];
 
char f (char c, int tip, int toggle) {
    if (tip == 0) c = '0'; else if (tip == 1) c = '1';
    if (toggle) {
        if (c == '0') c = '1'; else c = '0';
    }
    return c;
}
 
int calc (int pos, int tip, int toggle) {
    if (pos == n) return 0;
    if (dp[pos][tip][toggle] != -1) return dp[pos][tip][toggle];
    int res = 1e9;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 2; j++) {
            int cost = 0;
            if (i <= 1 && tip != i) cost++;
            if (j == 1 && toggle == 0) cost++;
            if (b[pos] == f(a[pos], i, j)) res =  min(res, cost + calc(pos + 1, i, j));
        }
    }
    return dp[pos][tip][toggle] = res;
}
 
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 2; j++) {
            int cost = 0;
            if (i <= 1) cost++;
            if (j == 1) cost++;
            sol = min(sol, cost + calc(0, i, j));
        }
    }
    cout << sol;
    return 0;
}

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