Submission #364645

#	Time	Username	Problem	Language	Result	Execution time	Memory
364645		parsabahrami	Lamps (JOI19_lamps)	C++17	100 / 100	78 ms	23020 KiB

lamp

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e6 + 10, MOD = 1e9 + 7;
int dp[N][3], A[N], B[N], n; char S[N];

int main() {
    scanf("%d", &n);
    scanf("%s", S + 1);
    for (int i = 1; i <= n; i++) A[i] = S[i] - '0';
    for (int i = 0; i < N; i++) dp[i][0] = dp[i][1] = dp[i][2] = MOD;
    scanf("%s", S + 1);
    dp[0][2] = 0;
    for (int i = 1; i <= n; i++) B[i] = S[i] - '0';
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                int x = dp[i][j];
                if (j != k && k != 2) x++;
                int a = (j == 0 ? 0 : (j == 1 ? 1 : A[i]));
                int b = (k == 0 ? 0 : (k == 1 ? 1 : A[i + 1]));
                if ((!i || a == B[i]) && b != B[i + 1]) x++;
                dp[i + 1][k] = min(dp[i + 1][k], x);
            }
        }
    } 
    printf("%d\n", min({dp[n][0], dp[n][1], dp[n][2]}));
    return 0;
}

Compilation message (stderr)

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

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