問題一覧 > 通常問題

No.2261 Coffee

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

問題文

あおば珈琲店には NN 種類の珈琲豆を売っています。
各珈琲豆には苦み、渋み、酸味、香り、コク という味のパラメータが決まっており、i (1iN)i\ (1\le i\le N) 番目の豆のパラメータの数値はそれぞれ Ai,Bi,Ci,Di,EiA_i,B_i,C_i,D_i,E_i です。
また、ii 番目の豆と jj 番目の豆の味の違い d(i,j)d(i,j)
d(i,j):=AiAj+BiBj+CiCj+DiDj+EiEjd(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,,Nk=1,2,\dots,N について、max1jNd(k,j)\displaystyle\max_{1\le j\le N}d(k,j) の値を答えてください。

入力

NN  
A1A_1 B1B_1 C1C_1 D1D_1 E1E_1  
A2A_2 B2B_2 C2C_2 D2D_2 E2E_2  
\vdots  
ANA_N BNB_N CNC_N DND_N ENE_N

  • 2N1052 \leq N \leq 10^5
  • 1Ai,Bi,Ci,Di,Ei10151 \leq A_i,B_i,C_i,D_i,E_i \leq 10^{15}
  • 入力はすべて整数

出力

NN 行にわたって出力してください。
kk (k=1,2,,N)(k=1,2,\dots,N) 行目には、max1jNd(k,j)\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番目の豆の味の違いは 12+44+14+49+24=11|1-2|+|4-4|+|1-4|+|4-9|+|2-4|=11
1番目と3番目の豆の味の違いは 12+46+14+45+27=12|1-2|+|4-6|+|1-4|+|4-5|+|2-7|=12
2番目と3番目の豆の味の違いは 22+46+44+95+47=9|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もしくは右上の雲マークをクリックしてアカウントを作成してください。