atcoder#ABC131B. [ABC131B] Bite Eating

[ABC131B] Bite Eating

题目描述

N N 個のリンゴがあります。これらはそれぞれリンゴ 1 1 、リンゴ 2 2 、リンゴ 3 3 、...、リンゴ N N と呼ばれており、リンゴ i i の「味」は L+i1 L+i-1 です。「味」は負になることもありえます。

また、1 1 個以上のリンゴを材料として、アップルパイをつくることができます。その「味」は、材料となったリンゴの「味」の総和となります。

あなたはこれらのリンゴを全て材料として、アップルパイをつくる予定でしたが、おなかがすいたので 1 1 個だけ食べることにしました。勿論、食べてしまったリンゴはアップルパイの材料にはできません。

つくる予定だったアップルパイとできるだけ同じものをつくりたいので、N N 個のリンゴ全てを材料としてできるアップルパイの「味」と、食べていない N1 N-1 個のリンゴを材料としてできるアップルパイの「味」の差の絶対値ができるだけ小さくなるように、食べるリンゴを選ぶことにしました。

このようにして選ばれたリンゴを食べた時、食べていない N1 N-1 個のリンゴを材料としてできるアップルパイの「味」を求めてください。

なお、この値は一意に定まることが証明できます。

输入格式

入力は以下の形式で標準入力から与えられます。

N N L L

输出格式

最適に食べるリンゴを選んだ時の、食べていない N1 N-1 個のリンゴを材料としてできるアップルパイの「味」を出力してください。

题目大意

N N 个苹果。苹果 i i 的“味道”是 L+i1 L+i-1 。“味道”也有可能是负的。

你可以用一个以上的苹果来制作苹果派。苹果派的“味道”是作为苹果的“味道”的总和。

因为肚子饿了,所以你吃了一个苹果。吃下去的苹果不能作为苹果派的材料。

想要尽量做出与预定的苹果派相同,即用没吃的 N1 N-1 个苹果做出的苹果派的“味道”要与用全部 N N 个苹果做出的苹果派的“味道”的绝对值的差尽可能小。

吃掉选出的最合适苹果,计算以未吃的 N1 N-1 个苹果做出的苹果派的“味道”。

另外,可以证明这个值是唯一确定的。

5 2
18
3 -1
0
30 -50
-1044

提示

制約

  • 2  N  200 2\ \leqq\ N\ \leqq\ 200
  • 100  L  100 -100\ \leqq\ L\ \leqq\ 100
  • 入力は全て整数である。

Sample Explanation 1

リンゴ 1,2,3,4,5 1,2,3,4,5 の「味」は、それぞれ 2,3,4,5,6 2,3,4,5,6 です。リンゴ 1 1 を食べるのが最適で、答えは 3+4+5+6=18 3+4+5+6=18 となります。

Sample Explanation 2

リンゴ 1,2,3 1,2,3 の「味」は、それぞれ 1,0,1 -1,0,1 です。リンゴ 2 2 を食べるのが最適で、答えは (1)+1=0 (-1)+1=0 となります。