問題一覧 > 通常問題

No.1150 シュークリームゲーム（Easy）

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 128
作問者 : Kiri8128 / テスター : tpyneriver
12 ProblemId : 4649 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-08 16:02:29

問題文

315さんと8128さんはシュークリームが大好きなので、2人でシュークリームゲームをしようとしています。
シュークリームゲームは、円形に配置された頂点を使って行うゲームです。 頂点は N 個あり、 各頂点には 1 から N までの番号が付いています。 頂点 i (1≤i≤N−1) と頂点 i+1 は隣り合っています。 また頂点 N と頂点 1 は隣り合っています。 これ以外の頂点の組み合わせは隣り合っていません。 頂点 i (1≤i≤N) には Ai 個のシュークリームが置かれています。 最初はどの頂点も占領されていません。

ゲームは次のように進行します。

まず315さんは頂点 s を占領し、そこに置いてあるシュークリームをすべて食べます。 また8128さんは頂点 t を占領し、そこに置いてあるシュークリームをすべて食べます。
次に315さんから始めて、すべての頂点がどちらかに占領されるまで、交互に次の操作を行います。

  • まだどちらにも占領されていない頂点のうち、自分が占領している頂点と隣り合う頂点を1つ選び、占領する
  • 占領した頂点に置かれているシュークリームをすべて食べる
最終的に315さんが食べたシュークリームを X 個、 8128さんが食べたシュークリームを Y 個とします。 315さんは X−Y を最大化したいですが、8128さんは X−Y を最小化したいです。 お互いが最善を尽くした場合、 X−Y はいくつになるでしょうか。

入力

N
s t
A1 A2 ⋯AN

4≤N≤105
1≤s, t≤N
s≠t
1≤Ai≤109 (1≤i≤N)
入力はすべて整数

出力

答えを1行に出力してください。 最後に改行してください。

サンプル

サンプル1
入力
4
1 3
10 20 50 100
出力
40

最初、315さんは頂点1の10個のシュークリームを、8128さんは頂点3の50個のシュークリームを食べます。
次に315さんは、20個のシュークリームが置かれた頂点2と100個のシュークリームが置かれた頂点4のうち1つを選ばないといけませんが、 頂点4を選ぶのが最善です。
次の8128さんのターンでは頂点2を選ぶしかありません。
315さんが食べたシュークリームは 10+100=110 個、 8128さんが食べたシュークリームは 50+20=70 個なので、 40 (=110−70) を出力します。

サンプル2
入力
7
1 7
10 20 30 40 50 60 70
出力
-80

7個の頂点があり、最初315さんは頂点1を、8128さんは頂点7を占領します。
その後、お互い各ターンで選べる頂点は1つしかありません。 315さんは頂点2, 3, 4を、8128さんは頂点6, 5を順に占領します。
315さんが食べたシュークリームは 10+20+30+40=100 個、 8128さんが食べたシュークリームは 70+60+50=180 個なので、 −80 (=100−180) を出力します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。