Submission #1182072

#TimeUsernameProblemLanguageResultExecution timeMemory
1182072avighnaLamps (JOI19_lamps)C++20
0 / 100
211 ms327680 KiB
#include <bits/stdc++.h>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  const int inf = 1e8;

  int n;
  std::cin >> n;
  std::string a, b;
  std::cin >> a >> b;

  auto range = [&](int s, int e, int t) {
    int ans = 0;
    int zca = 0, oca = 0;
    char prev_b = b[s];
    for (int i = s; i <= e; ++i) {
      if (b[i] != prev_b) {
        if (t == 1) {
          std::swap(zca, oca);
        }
        if (prev_b == '0') {
          ans += oca > 0;
        } else {
          ans += zca > 0;
        }
        zca = oca = 0;
      }
      zca += a[i] == '0', oca += a[i] == '1';
      prev_b = b[i];
    }
    if (t == 1) {
      std::swap(zca, oca);
    }
    if (prev_b == '0') {
      ans += oca > 0;
    } else {
      ans += zca > 0;
    }
    zca = oca = 0;
    return ans;
  };

  std::vector dp(n + 1, std::vector(n + 1, std::vector<int>(2)));
  for (int i = n; i >= 0; --i) {
    for (int b = n; b >= 0; --b) {
      for (int t = 0; t < 2; ++t) {
        if (i == n) {
          dp[i][b][t] = i == b ? 0 : inf;
          continue;
        }
        dp[i][b][t] = std::min(dp[i + 1][i + 1][1 - t] + range(b, i, t) + t,
                               dp[i + 1][b][t]);
      }
    }
  }
  std::cout << std::min(dp[0][0][0], dp[0][0][1]) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...