Submission #701673

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
701673	2023-02-21 22:32:21	PenguinsAreCute	Lamps (JOI19_lamps)	C++17	4 / 100	94 ms	49344 KiB

lamp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
int32_t main() {
    int N; cin >> N; string A, B; cin >> A >> B;
    int dp[N][3][2]; // idx, got 0 and got 1, got flip
    if(A[0] == B[0]) dp[0][0][0] = 0;
  else dp[0][0][0] = 1e15;
  if(B[0] == 0) dp[0][1][0] = 1;
  else dp[0][1][0] = 1e15;
  if(B[0] == 1) dp[0][2][0] = 1;
  else dp[0][2][0] = 1e15;
  if(A[0] != B[0]) dp[0][0][1] = 1;
  else dp[0][0][1] = 1e15;
  dp[0][1][1] = 2; dp[0][2][1] = 2;
    for(int i = 1; i < N; i++) {
    int minprev = 1e15;
    for(int j = 0; j < 3; j++) for(int k = 0; k < 2; k++) {
      minprev = min(minprev, dp[i - 1][j][k]);
    }
    if(A[i] == B[i]) dp[i][0][0] = minprev;
    else dp[i][0][0] = 1e15;
    if(B[i] == '0') dp[i][1][0] = min(minprev + 1, min(dp[i - 1][1][0], dp[i - 1][1][1]));
    else dp[i][1][0] = 1e15;
    if(B[i] == '1') dp[i][2][0] = min(minprev + 1, min(dp[i - 1][2][0], dp[i - 1][2][1]));
    else dp[i][2][0] = 1e15;
    if(A[i] != B[i]) dp[i][0][1] = min(minprev + 1, min(dp[i - 1][0][1], min(dp[i - 1][1][1], dp[i - 1][2][1])));
    else dp[i][0][1] = 1e15;
    dp[i][1][1] = min(minprev + 2, min(dp[i - 1][1][0], dp[i - 1][1][1]) + 1);
    dp[i][1][1] = min(dp[i][1][1], min(min(dp[i - 1][0][1], dp[i - 1][1][1]), dp[i - 1][2][1]) + 1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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