제출 #1149702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149702		fryingduc	Lamps (JOI19_lamps)	C++20	100 / 100	55 ms	25840 KiB

lamp

// https://oj.uz/submission/1054187
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e6 + 6;
int n;
string a, b;
int f[maxn][3][2];

void solve() {
  cin >> n >> a >> b;
  a = ' ' + a;
  b = ' ' + b;
  memset(f, 0x3f, sizeof(f));
  f[0][0][0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 2; ++k) {
        int cur = a[i] - '0';
        if (j == 1) cur = 0;
        if (j == 2) cur = 1;
        cur ^= k;
        for (int pj = 0; pj < 3; ++pj) {
          for (int pk = 0; pk < 2; ++pk) { 
            if (cur == b[i] - '0') {
              int cost = f[i - 1][pj][pk];
              cost += (pj != j and j > 0);
              cost += (k and !pk);
              f[i][j][k] = min(f[i][j][k], cost);
            }
          }
        }
      }
    }
  }
  int res = 1e9;
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 2; ++j) {
      res = min(res, f[n][i][j]);
    }
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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