제출 #210595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210595		Mamnoon_Siam	Lamps (JOI19_lamps)	C++17	100 / 100	189 ms	41620 KiB

lamp

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

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;

const int N = 1e6 + 6;

// msk = reset|set|toggle

int apply(int x, int msk) {
  int ret = x;
  if(msk & 4) ret = 0;
  if(msk & 2) ret = 1;
  if(msk & 1) ret ^= 1;
  return ret;
}

int dp[N][1 << 3];
int n;
vi A, B;

int main(int argc, char const *argv[])
{
  cin.sync_with_stdio(0); cin.tie(0);
  cin.exceptions(cin.failbit);
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  cin >> n;
  #define read(v) { string s; cin >> s; \
    for(int i = 0; i < n; i++) v.emplace_back(s[i] - '0'); }
  read(A); read(B);
  for(int u = 0; u < 8; u++) dp[n][u] = __builtin_popcount(u);
  for(int i = n-1; i >= 0; i--) {
    for(int u = 0; u < 8; u++) dp[i][u] = 1e9;
    for(int u = 0; u < 8; u++) if((u & 6) != 6) {
      for(int v = 0; v < 8; v++) if((v & 6) != 6) {
        if(apply(A[i], v) == B[i]) {
          dp[i][u] = min(dp[i][u], __builtin_popcount(u ^ v) + dp[i+1][v]);
        }
      }
    }
  }
  cout << dp[0][0] / 2 << endl;
  return 0;
}

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