제출 #233157

#제출 시각아이디문제언어결과실행 시간메모리
233157AlexLuchianovLamps (JOI19_lamps)C++14
100 / 100
120 ms22996 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 1000005;
int v[1 + nmax], v2[1 + nmax];
string s;

int dp[1 + nmax][3];

int extract(int x, int state){
  if(state == 2)
    return v[x] ^ v2[x];
  else
    return state ^ v2[x];
}

int main()
{
  int n;
  cin >> n;
  cin >> s;
  s = "#" + s;
  for(int i = 1; i <= n;i++)
    v[i] = s[i] - '0';
  cin >> s;
  s = "#" + s;
  for(int i = 1; i <= n;i++)
    v2[i] = s[i] - '0';
  dp[0][0] = dp[0][1] = nmax;
  dp[0][2] = 0;

  for(int i = 1;i <= n; i++){
    dp[i][0] = min(dp[i - 1][0] + (extract(i - 1, 0) ^ extract(i, 0)), dp[i - 1][2] + 2 + (extract(i - 1, 2) ^ extract(i, 0)));
    dp[i][1] = min(dp[i - 1][1] + (extract(i - 1, 1) ^ extract(i, 1)), dp[i - 1][2] + 2 + (extract(i - 1, 2) ^ extract(i, 1)));
    dp[i][2] = min(dp[i - 1][2] + (extract(i - 1, 2) ^ extract(i, 2)),
                   min(dp[i - 1][0] + (extract(i - 1, 0) ^ extract(i, 2)),
                       dp[i - 1][1] + (extract(i - 1, 1) ^ extract(i, 2))
                         ));
  }
  cout << (min(dp[n][0], min(dp[n][1], dp[n][2])) + 1) / 2;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...