Submission #118253

#	Time	Username	Problem	Language	Result	Execution time	Memory
118253		songc	Lamps (JOI19_lamps)	C++14	100 / 100	280 ms	29728 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

int N;
int A[1010101];
int B[1010101];
int D[1010101][5], ans=1234567890;
int C[5][5] ={
    {0, 1, 1, 2, 2},
    {0, 0, 1, 1, 2},
    {0, 1, 0, 2, 1},
    {0, 0, 1, 0, 2},
    {0, 1, 0, 2, 0}
};

int tog(int p, int o){
    int x = A[p];
    if (o == 1 || o == 4) x = 0;
    else if (o == 2 || o == 3) x = 1;
    return (x != B[p]) ? 1 : 0;
}

int main(){
    scanf("%d", &N);
    for (int i=1; i<=N; i++) scanf("%1d", &A[i]);
    for (int i=1; i<=N; i++) scanf("%1d", &B[i]);
    memset(D, 1, sizeof D);
    D[0][0] = 0;
    for (int i=1; i<=N; i++) for (int j=0; j<5; j++) for (int k=0; k<5; k++) {
        D[i][k] = min(D[i][k], D[i-1][j] + C[j][k] + max(0, tog(i, k)-tog(i-1, j)));
    }
    for (int i=0; i<5; i++) ans = min(ans, D[N][i]);
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
lamp.cpp:25:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=N; i++) scanf("%1d", &A[i]);
                              ~~~~~^~~~~~~~~~~~~~
lamp.cpp:26:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=N; i++) scanf("%1d", &B[i]);
                              ~~~~~^~~~~~~~~~~~~~

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