Submission #874000

#	Time	Username	Problem	Language	Result	Execution time	Memory
874000		vjudge1	Lamps (JOI19_lamps)	C++17	100 / 100	49 ms	51468 KiB

lamp

/// I'm only brave when I have to be
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL);
#define file_io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define FOR(i,k,n) for(int i = k; i < n; ++ i)
#define debf cout<<"(0-0)\n";
#define all(x) x.begin(), x.end()
#define dec(x) cout << fixed << setprecision(x);
#define pf push_front
#define ppf pop_front
#define dash " ------- "
#define what(x) cerr << #x << " is " << x << endl;
#define eb emplace_back
//#define int short int
#define int long long
#define sz(s) (int) (s.size())
#define fl cout.flush()

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef unsigned long long ull;
typedef long double ld;

template <class T> using max_heap = priority_queue <T, vector <T>, less <T> >;
template <class T> using min_heap = priority_queue <T, vector <T>, greater <T> >;

constexpr int MOD = 1e9 + 7, N = 1e6 + 8, M = 1e9, SQ = 500, INF = 1e9 + 8, LGN = 22, mod = 998244353, P = 131113;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, dp[N][3][2];
string s, t;

int32_t main(){
  fast_io;
  cin >> n >> s >> t;
  s = 'A' + s;
  t = 'A' + t;
  for (int i = 0; i <= n; ++ i){
    for (int j = 0; j < 3; ++ j){
      dp[i][j][0] = INF;
      dp[i][j][1] = INF;
    }
  }
  dp[0][2][0] = 0;
  for (int i = 1; i <= n; ++ i){
    for (int j = 0; j < 3; ++ j){
      for (int k = 0; k < 2; ++ k){
        int cur = 0;
        if (j == 2){
          cur = ((s[i] - '0') ^ k);
        }
        else {
          cur = (j ^ k);
        }
        if (cur == t[i] - '0'){
          for (int jj = 0; jj < 3; ++ jj){
            for (int kk = 0; kk < 2; ++ kk){
              int xx = 0;
              if (jj != j && j != 2){
                ++ xx;
              }
              if (k != kk && k == 1){
                ++ xx;
              }
              dp[i][j][k] = min (dp[i][j][k], dp[i-1][jj][kk] + xx);
            }
          }
        }
      }
    }
  }
  cout << min (dp[n][0][0], min (dp[n][0][1], min (dp[n][1][0], min (dp[n][1][1], min (dp[n][2][0], dp[n][2][1])))));
  return 0;
}

// Yesterday is history
// Tomorrow is a mystery
// but today is a gift
// That is why it is called the present

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