Submission #102515

#	Time	Username	Problem	Language	Result	Execution time	Memory
102515		ruhanhabib39	Lamps (JOI19_lamps)	C++17	100 / 100	49 ms	19988 KiB

lamp

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

const int INF = 1e9;
const int MAXN = 1e6;

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

int main() {
   scanf("%d%s%s", &N, A+1, B+1);
   A[0] = B[0] = '0';

   for(int i = 0; i <= N; i++) {
      for(int a : {0, 1}) {
         for(int t : {0, 1}) {
            dp[i][a][t] = INF;
         }
      }
   }

   dp[0][0][0] = 0;
   for(int i = 1; i <= N; i++) {
      {
         int& ref = dp[i][0][0];
         if(A[i] == B[i]) {
            ref = min({ref, dp[i-1][0][0], dp[i-1][0][1], dp[i-1][1][0], dp[i-1][1][1]});
         }
      }

      {
         int& ref = dp[i][0][1];
         if(A[i] != B[i]) {
            ref = min({ref, dp[i-1][0][0] + 1, dp[i-1][0][1], dp[i-1][1][0] + 1, dp[i-1][1][1]});
         }
      }

      {
         int& ref = dp[i][1][0];
         if(B[i-1] == B[i]) {
            ref = min({ref, dp[i-1][1][0]});
         }
         ref = min({ref, dp[i-1][0][0] + 1, dp[i-1][0][1] + 1, dp[i-1][1][1]});
      }

      {
         int& ref = dp[i][1][1];
         if(B[i-1] == B[i]) {
            ref = min({ref, dp[i-1][1][1]});
         } else {
            ref = min({ref, dp[i-1][1][0] + 1});
         }
         ref = min({ref, dp[i-1][0][0] + 2, dp[i-1][0][1] + 1});
      }

   }

   int res = INF;
   for(int a : {0, 1}) {
      for(int t : {0, 1}) {
         res = min(res, dp[N][a][t]);
      }
   }
   printf("%d\n", res);
}

Compilation message (stderr)

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