oj.uz

Submission #219313

# Submission time Handle Problem Language Result Execution time Memory
219313 2020-04-05T06:35:16 Z rama_pang Lamps (JOI19_lamps) C++14
4 / 100
 124 ms 65180 KB 
#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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 118 ms 65096 KB Output is correct
8 Correct 118 ms 65100 KB Output is correct
9 Correct 116 ms 65104 KB Output is correct
10 Correct 121 ms 65096 KB Output is correct
11 Correct 113 ms 65052 KB Output is correct
12 Correct 112 ms 65096 KB Output is correct
13 Correct 116 ms 65100 KB Output is correct
14 Correct 124 ms 65180 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -