No.1150 シュークリームゲーム（Easy）
タグ : / 解いたユーザー数 126
作問者 :
Kiri8128
/ テスター :
tpyneriver
問題文
315さんと8128さんはシュークリームが大好きなので、2人でシュークリームゲームをしようとしています。
シュークリームゲームは、円形に配置された頂点を使って行うゲームです。
頂点は $N$ 個あり、
各頂点には $1$ から $N$ までの番号が付いています。
頂点 $i\ (1 \le i \le N - 1)$ と頂点 $i+1$ は隣り合っています。
また頂点 $N$ と頂点 $1$ は隣り合っています。
これ以外の頂点の組み合わせは隣り合っていません。
頂点 $i\ (1 \le i \le N)$ には $A_i$ 個のシュークリームが置かれています。
最初はどの頂点も占領されていません。
ゲームは次のように進行します。
まず315さんは頂点 $s$ を占領し、そこに置いてあるシュークリームをすべて食べます。
また8128さんは頂点 $t$ を占領し、そこに置いてあるシュークリームをすべて食べます。
次に315さんから始めて、すべての頂点がどちらかに占領されるまで、交互に次の操作を行います。
- まだどちらにも占領されていない頂点のうち、自分が占領している頂点と隣り合う頂点を1つ選び、占領する
- 占領した頂点に置かれているシュークリームをすべて食べる
入力
$N$ $s\ t$ $A_1\ A_2\ \cdots A_N$
$4\le N\le 10^5$
$1\le s,\ t\le N$
$s\neq t$
$1\le A_i\le 10^9\ (1\le i\le 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もしくは右上の雲マークをクリックしてアカウントを作成してください。