Submission #233157

#	Time	Username	Problem	Language	Result	Execution time	Memory
233157		AlexLuchianov	Lamps (JOI19_lamps)	C++14	100 / 100	120 ms	22996 KiB

lamp

#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;
}

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