제출 #445727

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
445727	2021-07-19 12:10:07	egod1537	Lamps (JOI19_lamps)	C++14	4 / 100	23 ms	8320 KiB

lamp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int dp[1000001], sumA[4], sumB[4], mx[4];
bool prv[4];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n; cin >> n;
  string A, B; cin >> A >> B;
  prv[1] = prv[3] = true;
  memset(dp, 0x3f3f3f3f, sizeof(dp));
  dp[0] = 0;
  for (int i = 1; i <= n; i++) {
    int& ret = dp[i];
    if (!prv[0] && B[i-1] == '1') sumA[0]++;
    if (prv[0] && B[i-1] == '0') sumB[0]++;
    ret = min(ret, mx[0]+sumA[0] + 1);
    prv[0] = B[i-1] == '1';
    if (prv[1] && B[i-1] == '0') sumA[1]++;
    if (!prv[1] && B[i-1] == '1') sumB[1]++;
    ret = min(ret, mx[1] + sumA[1] + 1);
    prv[1] = B[i-1] == '1';
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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