Submission #216809

#	Time	Username	Problem	Language	Result	Execution time	Memory
216809		PeppaPig	Lamps (JOI19_lamps)	C++14	100 / 100	195 ms	121848 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+5;

int n, dp[N][3][2];
char A[N], B[N];

int solve(int i, int md, int f) {
    if(i == n + 1) return 0;
    int &now = dp[i][md][f];
    if(~now) return now;
    now = 1e9;

    for(int x = 0; x < 3; x++) for(int y = 0; y < 2; y++) {
        int cost = (x != md && x) + (y != f && y);
        int cur = !x ? A[i] - '0' : x - 1;
        if((cur ^ y) == B[i] - '0')
            now = min(now, solve(i + 1, x, y) + cost);
    }
    return now;
}

int main() {
    memset(dp, -1, sizeof dp);

    scanf("%d %s %s", &n, A + 1, B + 1);
    printf("%d\n", solve(1, 0, 0));

    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %s %s", &n, A + 1, B + 1);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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