Submission #126553

#	Time	Username	Problem	Language	Result	Execution time	Memory
126553		arnold518	Lamps (JOI19_lamps)	C++14	100 / 100	37 ms	16120 KiB

lamp

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N;
char A[MAXN+10], B[MAXN+10];
int dp[MAXN+10][3];

int main()
{
    int i, j;

    scanf("%d%s%s", &N, A+1, B+1);
    for(i=1; i<=N; i++) A[i]-='0', B[i]-='0';

    dp[1][0]=1+(B[1]!=0);
    dp[1][1]=1+(B[1]!=1);
    dp[1][2]=(A[1]!=B[1]);
    //printf("%d %d %d\n", dp[1][0], dp[1][1], dp[1][2]);
    for(i=2; i<=N; i++)
    {
        dp[i][0]=min(dp[i-1][0]+(B[i]!=0 && B[i-1]==0), dp[i-1][2]+1+(B[i]!=0 && A[i-1]==B[i-1]));
        dp[i][1]=min(dp[i-1][1]+(B[i]!=1 && B[i-1]==1), dp[i-1][2]+1+(B[i]!=1 && A[i-1]==B[i-1]));
        dp[i][2]=min(min(dp[i-1][0]+(A[i]!=B[i] && B[i-1]==0), dp[i-1][1]+(A[i]!=B[i] && B[i-1]==1)), dp[i-1][2]+(A[i]!=B[i] && A[i-1]==B[i-1]));
        //printf("%d %d %d\n", dp[i][0], dp[i][1], dp[i][2]);
    }
    printf("%d", min(dp[N][0], min(dp[N][1], dp[N][2])));
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:16:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
lamp.cpp:18: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