Submission #1183333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183333		avighna	Lamps (JOI19_lamps)	C++20	100 / 100	217 ms	198096 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;

  auto xor_val = [&](int i, int j) {
    if (i == n) {
      return 0;
    }
    return (j == 2 ? a[i] - '0' : j) ^ (b[i] - '0');
  };

  // try all 3^n bit strings:
  // dp[position][current character][sum of segments mod 2]
  // 0 => 0, 1 => 1, 2 => ?
  std::vector dp(n + 1, std::vector(3, std::vector<int>(2)));
  for (int i = n; i >= 0; --i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 2; ++k) {
        if (i == n) {
          dp[i][j][k] = j == 2 ? 0 : inf;
          continue;
        }
        int cur_xor = xor_val(i, j);
        if (j == 0) {
          // curr char = 0

          // 00, 01, 0?
          dp[i][j][k] = std::min(
              {dp[i + 1][0][k] + (cur_xor == 1 and xor_val(i + 1, 0) != 1),
               dp[i + 1][1][1 - k] + (k == 0) +
                   (cur_xor == 1 and xor_val(i + 1, 1) != 1),
               dp[i + 1][2][0] + (k == 0) +
                   (cur_xor == 1 and xor_val(i + 1, 2) != 1)});
        } else if (j == 1) {
          // curr char = 1

          // 10, 11, 1?
          dp[i][j][k] = std::min(
              {dp[i + 1][0][1 - k] + (k == 0) +
                   (cur_xor == 1 and xor_val(i + 1, 0) != 1),
               dp[i + 1][1][k] + (cur_xor == 1 and xor_val(i + 1, 1) != 1),
               dp[i + 1][2][0] + (k == 0) +
                   (cur_xor == 1 and xor_val(i + 1, 2) != 1)});
        } else {
          // curr char = ?

          // ?0, ?1, ??
          dp[i][j][k] = std::min(
              {dp[i + 1][0][1] + (cur_xor == 1 and xor_val(i + 1, 0) != 1) + 1,
               dp[i + 1][1][1] + (cur_xor == 1 and xor_val(i + 1, 1) != 1) + 1,
               dp[i + 1][2][0] + (cur_xor == 1 and xor_val(i + 1, 2) != 1)});
        }
      }
    }
  }

  std::cout << std::min({dp[0][0][1] + 1, dp[0][1][1] + 1, dp[0][2][0]})
            << '\n';
}

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