問題一覧 > 通常問題

No.2261 Coffee

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 136
作問者 : karinohitokarinohito / テスター : とりゐとりゐ sotanishysotanishy
7 ProblemId : 9366 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-07 21:18:21

問題文

あおば珈琲店には $N$ 種類の珈琲豆を売っています。
各珈琲豆には苦み、渋み、酸味、香り、コク という味のパラメータが決まっており、$i\ (1\le i\le N)$ 番目の豆のパラメータの数値はそれぞれ $A_i,B_i,C_i,D_i,E_i$ です。
また、$i$ 番目の豆と $j$ 番目の豆の味の違い $d(i,j)$ は
$$d(i,j):=|A_i-A_j|+|B_i-B_j|+|C_i-C_j|+|D_i-D_j|+|E_i-E_j|$$
で表されます。
この店に訪れたひろせさんは2種類の豆を買うことにしました。
ひろせさんは様々な珈琲を楽しみたいので味の違いが大きくなるように2種類の豆を買うことにしました。
$k=1,2,\dots,N$ について、$\displaystyle\max_{1\le j\le N}d(k,j)$ の値を答えてください。

入力

$N$  
$A_1$ $B_1$ $C_1$ $D_1$ $E_1$  
$A_2$ $B_2$ $C_2$ $D_2$ $E_2$  
$\vdots$  
$A_N$ $B_N$ $C_N$ $D_N$ $E_N$

  • $2 \leq N \leq 10^5$
  • $1 \leq A_i,B_i,C_i,D_i,E_i \leq 10^{15}$
  • 入力はすべて整数

出力

$N$ 行にわたって出力してください。
$k$ $(k=1,2,\dots,N)$ 行目には、$\displaystyle\max_{1\le j\le N}d(k,j)$ の値を出力してください。

サンプル

サンプル1
入力
3
1 4 1 4 2
2 4 4 9 4
2 6 4 5 7
出力
12
11
12

1番目と2番目の豆の味の違いは $|1-2|+|4-4|+|1-4|+|4-9|+|2-4|=11$
1番目と3番目の豆の味の違いは $|1-2|+|4-6|+|1-4|+|4-5|+|2-7|=12$
2番目と3番目の豆の味の違いは $|2-2|+|4-6|+|4-4|+|9-5|+|4-7|=9$
です。

サンプル2
入力
5
94141 61516 1160 84124 461413
1146 8242367237 6623526 79272 153
96246 7512214 17138569 151611 1783836210
512415 192720 245373478 18932163 431516435
91241 1 10243532362 8176947 1275254151
出力
11526481178
19762717840
10750518406
10853265709
19762717840

サンプル3
入力
3  
3 1 4 1 5  
3 1 4 1 5  
3 1 4 1 5  
出力
0
0
0

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