F - Yakiniku Restaurants

Contest Duration: 2017-01-15(Sun) 12:00 - 2017-01-15(Sun) 13:40 (local time) (100 minutes) Back to Home

F - Yakiniku Restaurants Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : $1000$ 点

問題文

$1$ から $N$ までの番号のついた $N$ 軒の焼肉店があります。焼肉店は番号順に一直線上に並んでいて、 $i$ 番目の焼肉店と $i+1$ 番目の焼肉店の距離は $A_i$ です。

joisinoお姉ちゃんは、 $1$ から $M$ までの番号のついた $M$ 枚のチケットを持っています。どの焼肉店でも、これらのチケットと引き換えに焼き肉を食べられます。 $i$ 番目の焼肉店で、 $j$ 番目のチケットと引き換えに食べられる焼き肉の美味しさは $B_{i,j}$ です。一度使ったチケットは $2$ 度以上使えません。また、同じ焼肉店で使うチケットの数に制限はありません。

joisinoお姉ちゃんは、適当な焼肉店の前からスタートして、別の焼肉店の場所へ移動したり、目の前にある焼肉店でまだ使っていないチケットを使って焼き肉を食べたりすることを繰り返して、 $M$ 枚の焼き肉を食べようとしています。 joisinoお姉ちゃんの最終的な幸福度は、「食べた焼き肉の美味しさの総和 $-$ 移動した距離の合計」で求められます。 joisinoお姉ちゃんの最終的な幸福度の最大値を求めてください。

制約

入力は全て整数である
$2≦N≦5×10^3$
$1≦M≦200$
$1≦A_i≦10^9$
$1≦B_{i,j}≦10^9$

入力

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

 $N$   $M$ 
 $A_1$   $A_2$   $...$   $A_{N-1}$ 
 $B_{1,1}$   $B_{1,2}$   $...$   $B_{1,M}$ 
 $B_{2,1}$   $B_{2,2}$   $...$   $B_{2,M}$ 
 $:$ 
 $B_{N,1}$   $B_{N,2}$   $...$   $B_{N,M}$

出力

joisinoお姉ちゃんの最終的な幸福度の最大値を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

$1$ 番目の焼肉店の前からスタートし、 $1$ 番目と $3$ 番目のチケットを使って焼き肉を食べたあと、 $2$ 番目の焼肉店の前まで移動して、 $2$ 番目と $4$ 番目のチケットを使って焼き肉を食べると、幸福度を最大化できます。

入力例 2Copy

Copy

出力例 2Copy

Copy

Score : $1000$ points

Problem Statement

There are $N$ barbecue restaurants along a street. The restaurants are numbered $1$ through $N$ from west to east, and the distance between restaurant $i$ and restaurant $i+1$ is $A_i$ .

Joisino has $M$ tickets, numbered $1$ through $M$ . Every barbecue restaurant offers barbecue meals in exchange for these tickets. Restaurant $i$ offers a meal of deliciousness $B_{i,j}$ in exchange for ticket $j$ . Each ticket can only be used once, but any number of tickets can be used at a restaurant.

Joisino wants to have $M$ barbecue meals by starting from a restaurant of her choice, then repeatedly traveling to another barbecue restaurant and using unused tickets at the restaurant at her current location. Her eventual happiness is calculated by the following formula: "(The total deliciousness of the meals eaten) - (The total distance traveled)". Find her maximum possible eventual happiness.

Constraints

All input values are integers.
$2≤N≤5×10^3$
$1≤M≤200$
$1≤A_i≤10^9$
$1≤B_{i,j}≤10^9$

Input

The input is given from Standard Input in the following format:

 $N$   $M$ 
 $A_1$   $A_2$   $...$   $A_{N-1}$ 
 $B_{1,1}$   $B_{1,2}$   $...$   $B_{1,M}$ 
 $B_{2,1}$   $B_{2,2}$   $...$   $B_{2,M}$ 
 $:$ 
 $B_{N,1}$   $B_{N,2}$   $...$   $B_{N,M}$

Output

Print Joisino's maximum possible eventual happiness.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

The eventual happiness can be maximized by the following strategy: start from restaurant $1$ and use tickets $1$ and $3$ , then move to restaurant $2$ and use tickets $2$ and $4$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy