Submission #1183337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183337		avighna	Lamps (JOI19_lamps)	C++20	100 / 100	200 ms	198100 KiB

lamp

#include <bits/stdc++.h>

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

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

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

  std::vector dp(n + 1, std::vector(3, std::vector<int>(2)));
  dp[n][0][0] = dp[n][1][1] = dp[n][0][1] = dp[n][1][0] = 1e8;
  for (int i = n - 1; i >= 0; --i) {
    for (int k = 0; k < 2; ++k) {
      dp[i][0][k] = std::min(
          {dp[i + 1][0][k] + (f(i, 0) and !f(i + 1, 0)),
           dp[i + 1][1][!k] + !k + (f(i, 0) and !f(i + 1, 1)),
           dp[i + 1][2][0] + !k + (f(i, 0)  and !f(i + 1, 2))});
      dp[i][1][k] = std::min(
          {dp[i + 1][0][!k] + !k + (f(i, 1) and !f(i + 1, 0)),
           dp[i + 1][1][k] + (f(i, 1) and !f(i + 1, 1)),
           dp[i + 1][2][0] + !k + (f(i, 1) and !f(i + 1, 2))});
      dp[i][2][k] = std::min(
          {dp[i + 1][0][1] + (f(i, 2)  and !f(i + 1, 0)) + 1,
           dp[i + 1][1][1] + (f(i, 2) and !f(i + 1, 1)) + 1,
           dp[i + 1][2][0] + (f(i, 2)  and !f(i + 1, 2))});
    }
  }

  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