Submission #1182984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182984		avighna	Lamps (JOI19_lamps)	C++20	0 / 100	212 ms	327680 KiB

lamp

#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;
  std::string b_tog(n, '0');
  for (int i = 0; i < n; ++i) {
    b_tog[i] = b[i] == '0' ? '1' : '0';
  }

  auto range = [&](int s, int e, int t) {
    if (t == 1) {
      std::swap(b, b_tog);
    }
    int ans = 0;
    int zca = 0, oca = 0;
    char prev_b = b[s];
    int oseg = 0, zseg = 0;
    bool all_o = true, all_z = true;
    for (int i = s; i <= e; ++i) {
      all_o = all_o and a[i] == '1';
      all_z = all_z and a[i] == '0';
      if (b[i] != prev_b) {
        oseg += prev_b == '1';
        zseg += prev_b == '0';
        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];
    }
    oseg += prev_b == '1';
    zseg += prev_b == '0';
    if (prev_b == '0') {
      ans += oca > 0;
    } else {
      ans += zca > 0;
    }
    zca = oca = 0;
    if (t == 1) {
      std::swap(b, b_tog);
    }
    return std::min({ans, oseg + !all_z, zseg + !all_o});
  };

  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;
        }
        if (b > i) {
          dp[i][b][t] = 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';
}

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