(cache)H - Tokaido

コンテスト時間: 2016-11-26(土) 03:30 ~ 2016-11-26(土) 06:30 (180分)

H - Tokaido 解説

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : $1600$ 点

問題文

$N$ 個のマスが一列に並んでおり、左から順に $1 ～ N$ の番号が付けられています。すぬけくんとりんごさんはこのマス目を使って、以下のようなボードゲームで遊ぼうとしています。

はじめに、すぬけくんがすべてのマスに $1$ つずつ整数を書く。
$2$ 人のプレイヤーはそれぞれ $1$ つずつ駒を用意し、すぬけくんは自分の駒をマス $1$ に、りんごさんは自分の駒をマス $2$ に置く。
自分の駒が相手の駒より左にあるプレイヤーが駒を動かす。駒を動かす先は、今自分の駒が置かれているマスよりも右にあってかつ相手の駒が置かれていないマスでなければならない。
3. を繰り返し、これ以上駒を動かすことができなくなるとゲームは終了となる。
ゲーム終了時までに自分の駒を置いたことのあるマスに書かれた整数の合計が、それぞれのプレイヤーのスコアとなる。

すぬけくんはすでにマス $i (1 ≦ i ≦ N - 1)$ に整数 $A_{i}$ を書きましたが、まだマス $N$ には整数を書いていません。すぬけくんは $M$ 個の整数 $X_{1}, X_{2}, . . ., X_{M}$ それぞれについて、その数をマス $N$ に書いてゲームを行ったときに「（すぬけくんのスコア）ー（りんごさんのスコア）」がいくらになるのかを計算することにしました。ただし、それぞれのプレイヤーは「（自分のスコア）ー（相手のスコア）」を最大化するように駒を動かすものとします。

制約

$3 ≦ N ≦ 200, 000$
$0 ≦ A_{i} ≦ 10^{6}$
$A_{i}$ の総和は $10^{6}$ 以下である。
$1 ≦ M ≦ 200, 000$
$0 ≦ X_{i} ≦ 10^{9}$

部分点

$M = 1$ を満たすデータセットに正解した場合は、 $700$ 点が与えられる。
追加制約のないデータセットに正解した場合は、上記とは別に $900$ 点が与えられる。

入力

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

 $N$ 
 $A_{1}$   $A_{2}$   $. . .$   $A_{N - 1}$ 
 $M$ 
 $X_{1}$ 
 $X_{2}$ 
 $:$ 
 $X_{M}$

出力

$X_{1} \dots X_{M}$ の $M$ 個の整数それぞれに対し、その数をマス $N$ に書いたときの「（すぬけくんのスコア）ー（りんごさんのスコア）」を $1$ 行にひとつずつ出力せよ。

入力例 1 Copy

Copy

出力例 1 Copy

Copy

ゲームは下図のように進行します。Sはすぬけくんの駒、Rはりんごさんの駒を表しています。

スコアは $2$ 人とも $10$ となり、「（すぬけくんのスコア）ー（りんごさんのスコア）」は $0$ となります。

入力例 2 Copy

Copy

9
2 0 1 6 1 1 2 6
5
2016
1
1
2
6

出力例 2 Copy

Copy

Score : points

There are squares in a row, numbered through from left to right. Snuke and Rng are playing a board game using these squares, described below:

Each of the two players possesses one piece. Snuke places his piece onto square , and Rng places his onto square .

Snuke has already written an integer into square , but not into square yet. He has decided to calculate for each of integers , if he writes it into square and the game is played, what the value "(Snuke's score) - (Rng's score)" will be. Here, it is assumed that each player moves his piece to maximize the value "(the player's score) - (the opponent's score)".

The sum of all is at most .

points will be awarded for passing the test set satisfying .
Additional points will be awarded for passing the test set without additional constraints.

For each of the integers , print the value "(Snuke's score) - (Rng's score)" if it is written into square , one per line.

Both player scores , thus "(Snuke's score) - (Rng's score)" is .