Submission #166865

#	Time	Username	Problem	Language	Result	Execution time	Memory
166865		Akashi	Lamps (JOI19_lamps)	C++14	100 / 100	132 ms	27840 KiB

lamp

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

const int INF = 1e9;

int n;
char a[1000005];
char b[1000005];
int d[1000005][3][2];

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

    for(int j = 0; j < 3 ; ++j)
        for(int t = 0; t < 2 ; ++t)
            d[0][j][t] = INF;
    d[0][0][0] = 0;

    for(int i = 1; i <= n ; ++i){
        for(int j = 0; j < 3 ; ++j)
            for(int t = 0; t < 2 ; ++t)
                d[i][j][t] = INF;

        for(int j = 0; j < 3 ; ++j){
            for(int t = 0; t < 2 ; ++t){
                int val = 0;
                if(j == 0) val = a[i] - '0';
                else val = j - 1;
                if(t == 1) val = 1 - val;

                if(val != b[i] - '0') continue ;
                for(int j2 = 0; j2 < 3 ; ++j2)
                    for(int t2 = 0; t2 < 2 ; ++t2)
                        d[i][j][t] = min(d[i][j][t], d[i - 1][j2][t2] + ((j != j2) & (j > 0)) + ((t != t2) & (t > 0)));
            }
        }
    }

    int Sol = INF;
    for(int j = 0; j < 3 ; ++j)
        for(int t = 0; t < 2 ; ++t)
            Sol = min(Sol, d[n][j][t]);

    printf("%d", Sol);

    return 0;
}

Compilation message (stderr)

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

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