Submission #219318

#	Time	Username	Problem	Language	Result	Execution time	Memory
219318		rama_pang	Lamps (JOI19_lamps)	C++14	100 / 100	142 ms	66468 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e7;

int N;
string A, B;

void Read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> A >> B;
}

int Solve() {
  vector<array<array<int, 4>, 4>> dp(N + 1); // dp[pos][second_last_operation][last_operation]
  // dp[pos] means A[pos...N] = B[pos...N]
  // operation 0 = skip operation
  // operation 1 = off operation
  // operation 2 = on operation
  // operation 3 = xor operation

  for (int i = 0; i <= N; i++) {
    for (int j = 0; j < 4; j++) {
      for (int k = 0; k < 4; k++) { 
        dp[i][j][k] = INF;
      }
    }
  }

  dp[0][0][0] = 0;
  for (int pos = 0; pos < N; pos++) {
    // merge operation
    if (B[pos] == '0') {
      dp[pos + 1][0][1] = min(dp[pos + 1][0][1], dp[pos][1][2]); // off on off (from off off/on off)
      dp[pos + 1][0][1] = min(dp[pos + 1][0][1], dp[pos][3][2]); // xor on off (from xor off/xor off)
    }
    if (B[pos] == '1') {
      dp[pos + 1][0][2] = min(dp[pos + 1][0][2], dp[pos][2][1]); // on off on (from on on/off on)
      dp[pos + 1][0][2] = min(dp[pos + 1][0][2], dp[pos][3][1]); // xor off on (from xor on/xor on)
    }
    if (A[pos] != B[pos]) {
      dp[pos + 1][0][3] = min(dp[pos + 1][0][3], dp[pos][1][2]); // off on xor (from off off/xor xor)
      dp[pos + 1][0][3] = min(dp[pos + 1][0][3], dp[pos][2][1]); // on off xor (from on on/xor xor)
      dp[pos + 1][0][3] = min(dp[pos + 1][0][3], dp[pos][3][2]); // xor on xor (from xor xor/on xor)
      dp[pos + 1][0][3] = min(dp[pos + 1][0][3], dp[pos][3][1]); // xor off xor (from xor xor/off xor)
    }


    for (int second_last = 0; second_last < 4; second_last++) {
      // extend last operation
      if (A[pos] == B[pos]) { // operation skip (0)
        dp[pos + 1][second_last][0] = min(dp[pos + 1][second_last][0], dp[pos][second_last][0]);
      }
      if (B[pos] == '0') { // operation off (1)
        dp[pos + 1][second_last][1] = min(dp[pos + 1][second_last][1], dp[pos][second_last][1]);
      }
      if (B[pos] == '1') { // operation on (2)
        dp[pos + 1][second_last][2] = min(dp[pos + 1][second_last][2], dp[pos][second_last][2]);
      }
      if (A[pos] != B[pos]) { // operation xor (3)
        dp[pos + 1][second_last][3] = min(dp[pos + 1][second_last][3], dp[pos][second_last][3]);
      }


      // new operation
      for (int last = 0; last < 4; last++) {
        if (A[pos] == B[pos]) { // operation skip (0)
          dp[pos + 1][last][0] = min(dp[pos + 1][last][0], dp[pos][second_last][last]);
        }
        if (B[pos] == '0') { // operation off (1)
          dp[pos + 1][last][1] = min(dp[pos + 1][last][1], 1 + dp[pos][second_last][last]);
        }
        if (B[pos] == '1') { // operation on (2)
          dp[pos + 1][last][2] = min(dp[pos + 1][last][2], 1 + dp[pos][second_last][last]);
        }
        if (A[pos] != B[pos]) { // operation xor (3)
          dp[pos + 1][last][3] = min(dp[pos + 1][last][3], 1 + dp[pos][second_last][last]);
        }
      }
    }
  }  

  int res = INF;
  for (int second_last = 0; second_last < 4; second_last++) {
    for (int last = 0; last < 4; last++) {
      res = min(res, dp[N][second_last][last]);
    }
  }

  return res;
}

int main() {
  Read();
  cout << Solve() << "\n";
  return 0;
}

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