[CodeForces1000]B. Light It Up

2018-06-28

lolifamily

题解

贪心

一道贪心的简单题，插入无非就是两种情况：

在开灯的区间内插入，应该让插入的元素尽可能地靠后
在关灯的区间内插入，应该让插入的元素尽可能地靠前

注意：

g1 和 g2 的含义，g1 是指不落单（最后两次操作刚好完成一次开关）的后缀和，而 g2 则指的是会落单的后缀和
i+1 和 i+2 的选择，应该在纸上画图而不是凭空乱想
因为 n 的奇偶性不知道，所以 ans 的初始值为末尾两个数的最大值

B. Light It Up

time limit per test: 1 secondmemory limit per test: 256 megabytesinput: standard inputoutput: standard output

Recently, you bought a brand new smart lamp with programming features. At first, you set up a schedule to the lamp. Every day it will turn power on at moment $0$ and turn power off at moment $𝑀$ . Moreover, the lamp allows you to set a program of switching its state (states are “lights on” and “lights off”). Unfortunately, some program is already installed into the lamp.

The lamp allows only good programs. Good program can be represented as a non-empty array $𝑎$ , where $0 < 𝑎 1 < 𝑎 2 < \dots < 𝑎 | 𝑎 | < 𝑀$ . All $𝑎 𝑖$ must be integers. Of course, preinstalled program is a good program.

The lamp follows program $𝑎$ in next manner: at moment $0$ turns power and light on. Then at moment $𝑎 𝑖$ the lamp flips its state to opposite (if it was lit, it turns off, and vice versa). The state of the lamp flips instantly: for example, if you turn the light off at moment $1$ and then do nothing, the total time when the lamp is lit will be $1$ . Finally, at moment $𝑀$ the lamp is turning its power off regardless of its state.

Since you are not among those people who read instructions, and you don’t understand the language it’s written in, you realize (after some testing) the only possible way to alter the preinstalled program. You can insert at most one element into the program $𝑎$ , so it still should be a good program after alteration. Insertion can be done between any pair of consecutive elements of $𝑎$ , or even at the begining or at the end of $𝑎$ .

Find such a way to alter the program that the total time when the lamp is lit is maximum possible. Maybe you should leave program untouched. If the lamp is lit from $𝑥$ till moment $𝑦$ , then its lit for $𝑦 - 𝑥$ units of time. Segments of time when the lamp is lit are summed up.

Input

First line contains two space separated integers $𝑛$ and $𝑀$ ( $1 \leq 𝑛 \leq 105$ , $2 \leq 𝑀 \leq 109$ ) — the length of program $𝑎$ and the moment when power turns off.

Second line contains $𝑛$ space separated integers $𝑎 1, 𝑎 2, \dots, 𝑎 𝑛$ ( $0 < 𝑎 1 < 𝑎 2 < \dots < 𝑎 𝑛 < 𝑀$ ) — initially installed program $𝑎$ .

Output

Print the only integer — maximum possible total time when the lamp is lit.

Examples

input

output

1
8

input

output

1
9

input

output

1
6

Note

In the first example, one of possible optimal solutions is to insert value $𝑥 = 3$ before $𝑎 1$ , so program will be $[3, 4, 6, 7]$ and time of lamp being lit equals $(3 - 0) + (6 - 4) + (10 - 7) = 8$ . Other possible solution is to insert $𝑥 = 5$ in appropriate place.

In the second example, there is only one optimal solution: to insert $𝑥 = 2$ between $𝑎 1$ and $𝑎 2$ . Program will become $[1, 2, 10]$ , and answer will be $(1 - 0) + (10 - 2) = 9$ .

In the third example, optimal answer is to leave program untouched, so answer will be $(3 - 0) + (7 - 4) = 6$ .

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
int a[100005],f[100005],g1[100005],g2[100005];
7
int main(void)
8
{
9
  int i,n,m,ans=0;
10
  scanf("%d%d",&n,&m);
11
  for(i=1;i<=n;++i)scanf("%d",&a[i]);
12
  a[n+1]=m;
13
  for(i=1;i<=n+2;i+=2)f[i]=f[i-2]+a[i]-a[i-1];
14
  for(i=n;i>=1;i-=2)g1[i]=g1[i+2]+a[i+1]-a[i];
15
  for(i=n-1;i>=1;i-=2)g2[i]=g2[i+2]+a[i+1]-a[i];
16
  ans=max(f[n+1],f[n]);
17
  if(n%2==0)
18
  {
19
    for(i=1;i<=n+1;i+=2)
20
    {
21
      if(a[i]-a[i-1]<=1)continue;
22
      ans=max(ans,f[i]-1+g2[i]);
23
    }
24
    for(i=1;i<=n;i+=2)
25
    {
26
      if(a[i+1]-a[i]<=1)continue;
27
      ans=max(ans,f[i]+a[i+1]-a[i]-1+g2[i+2]);
28
    }
29
  }
30
  else
31
  {
32
    for(i=1;i<=n+1;i+=2)
33
    {
34
      if(a[i]-a[i-1]<=1)continue;
35
      ans=max(ans,f[i]-1+g1[i]);
36
    }
37
    for(i=1;i<=n;i+=2)
38
    {
39
      if(a[i+1]-a[i]<=1)continue;
40
      ans=max(ans,f[i]+a[i+1]-a[i]-1+g1[i+2]);
41
    }
42
  }
43
  printf("%d\n",ans);
44
  return 0;
45
}