Submission #965024

#	Time	Username	Problem	Language	Result	Execution time	Memory
965024		abczz	Lamps (JOI19_lamps)	C++14	100 / 100	431 ms	98456 KiB

lamp

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll long long

using namespace std;

ll n, f = 1e18, dp[1000000][12];
string S, T;

ll get(ll u, vector <ll> state) {
  ll mn = 1e18;
  for (auto v : state) mn = min(mn, dp[u][v]);
  return mn;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> S >> T;
  for (int i=0; i<n; ++i) {
    for (int j=0; j<12; ++j) dp[i][j] = 1e18;
    if (S[i] != T[i]) {
      if (!i) dp[i][2] = 1;
      else dp[i][2] = min(get(i-1, {2, 3, 4, 5, 6, 7, 8}), get(i-1, {0, 1, 9, 10, 11})+1);
    }
    else {
      if (!i) dp[i][9] = 0;
      else {
        for (int j=0; j<12; ++j) {
          dp[i][9] = min(dp[i][9], dp[i-1][j]);
        }
      }
    }
    if (T[i] == '0') {
      if (!i) dp[i][0] = 1, dp[i][4] = dp[i][5] = dp[i][11] = 2, dp[i][8] = 3;
      else {
        dp[i][0] = min(get(i-1, {0, 3, 5, 7, 8, 10, 11}), get(i-1, {1, 2, 4, 6, 9})+1);
        dp[i][4] = min(get(i-1, {4}), min(get(i-1, {1, 2, 3, 5, 6, 7, 8, 10, 11})+1, get(i-1, {0, 9})+2));
        dp[i][5] = min(get(i-1, {5, 7, 8}), min(get(i-1, {0, 2, 3, 4, 6, 10, 11})+1, get(i-1, {1, 9})+2));
        dp[i][8] = min(get(i-1, {8}), min(get(i-1, {5, 6, 7, 11})+1, min(get(i-1, {0, 1, 2, 3, 4, 10})+2, get(i-1, {9})+3)));
        dp[i][11] = min(get(i-1, {8, 11}), min(get(i-1, {0, 1, 3, 4, 5, 6, 7, 10})+1, get(i-1, {2, 9})+2));
      }
    }
    else {
      if (!i) dp[i][1] = 1, dp[i][3] = dp[i][6] = dp[i][10] = 2, dp[i][7] = 3;
      else {
        dp[i][1] = min(get(i-1, {1, 4, 6, 7, 8, 10, 11}), get(i-1, {0, 2, 3, 5, 9})+1);
        dp[i][3] = min(get(i-1, {3}), min(get(i-1, {0, 2, 4, 5, 6, 7, 8, 10, 11})+1, get(i-1, {1, 9})+2));
        dp[i][6] = min(get(i-1, {6, 7, 8}), min(get(i-1, {1, 2, 3, 4, 5, 10, 11})+1, get(i-1, {0, 9}))+2);
        dp[i][7] = min(get(i-1, {7}), min(get(i-1, {5, 6, 8, 10})+1, min(get(i-1, {0, 1, 2, 3, 4, 11})+2, get(i-1, {9})+3)));
        dp[i][10] = min(get(i-1, {7, 10}), min(get(i-1, {0, 1, 3, 4, 5, 6, 8, 11})+1, get(i-1, {2, 9})+2));
      }
    }
  }
  for (int j=0; j<12; ++j) {
    f = min(f, dp[n-1][j]);
  }
  cout << f << '\n';
}

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