제출 #1185475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185475		mannshah1211	Lamps (JOI19_lamps)	C++20	100 / 100	85 ms	57168 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "deb.h"
#else
#define debug(...) 
#endif

#define pb emplace_back
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < n; i++) 
#define per(i, n) for (int i = n - 1; i >= 0; i--) 
#define sz(a) (int) (a).size()

using vi = vector<int>;
using ll = long long;

const int inf = int(1e9);

void solve() {
  int n;
  cin >> n;
  string a, b;
  cin >> a >> b;
  a = '$' + a;
  b = '$' + b;
  auto Get = [&](char c, int state) {
    if (state == 0) {
      return '0';
    } else if (state == 1) {
      return '1'; 
    } else {
      return c;
    }
  };
  vector<vi> dp(n + 1, vi(3, inf));
  dp[0][2] = 0;
  rep(i, n + 1) {
    rep(cur, 3) {
      rep(prev, 3) {
        if (i == 0) {
          continue;
        }
        int v = dp[i - 1][prev];
        if (cur != prev && cur != 2) {
          v++;
        }
        if ((i == 1 || Get(a[i - 1], prev) == b[i - 1]) && (Get(a[i], cur) != b[i])) {
          v++;
        }
        dp[i][cur] = min(dp[i][cur], v);
      }
    }
  }
  cout << *min_element(dp[n].begin(), dp[n].end()) << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

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