Submission #157020

#	Time	Username	Problem	Language	Result	Execution time	Memory
157020		EntityIT	Lamps (JOI19_lamps)	C++14	100 / 100	131 ms	26104 KiB

lamp

#include<bits/stdc++.h>

using namespace std;

const int N = (int)1e6 + 5, inf = (int)1e9 + 123;
int n, f[N][3][2];
char a[N], b[N];

int main() {
    scanf(" %d %s %s", &n, a + 1, b + 1);

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 2; ++k) f[i][j][k] = inf;
        }
    }
    f[0][0][0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 2; ++k) if (f[i][j][k] < inf) {
                for (int nJ = 0; nJ < 3; ++nJ) {
                    for (int nK = 0; nK < 2; ++nK) {
                        char after = a[i + 1];
                        if (nJ == 1) after = '0';
                        else if (nJ == 2) after = '1';
                        if (nK) after = (after == '0' ? '1' : '0');
                        if (after != b[i + 1]) continue ;
                        f[i + 1][nJ][nK] = min(f[i + 1][nJ][nK], f[i][j][k] + (nJ && j != nJ) + (nK && k != nK) );
                    }
                }
            }
        }
    }

    int ans = inf;
    for (int j = 0; j < 3; ++j) {
        for (int k = 0; k < 2; ++k) ans = min(ans, f[n][j][k]);
    }

    printf("%d", ans);

    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:10: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