F - Maximum Composition

Contest Duration: 2024-08-10(Sat) 12:00 - 2024-08-10(Sat) 13:40 (local time) (100 minutes) Back to Home

F - Maximum Composition Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$N$ 個の一次関数 $f_1,f_2,\ldots,f_N$ が与えられます。 $f_i(x)=A_i x+B_i$ です。

$1$ 以上 $N$ 以下の相異なる $K$ 個の整数からなる長さ $K$ の数列 $p=(p_1,p_2, \ldots p_K)$ について、 $f_{p_1}(f_{p_2}(\ldots f_{p_K}(1)\ldots ))$ としてありえる最大値を求めてください。

制約

$1 \leq N \leq 2 \times 10^{5}$
$1 \leq K \leq \text{min}(N,10)$
$1 \leq A_i,B_i \leq 50$ $(1 \leq i \leq N)$
入力はすべて整数

入力

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

 $N$   $K$ 
 $A_1$   $B_1$ 
 $A_2$   $B_2$ 
 $\vdots$ 
 $A_N$   $B_N$

出力

答えを整数として出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

ありえるすべての $p$ とそれに対応する $f_{p_1}(f_{p_2}(1))$ の値は以下の通りです。

$p= ( 1,2 )$ : $f_1(f_2(1))=15$
$p= ( 1,3 )$ : $f_1(f_3(1))=15$
$p= ( 2,1 )$ : $f_2(f_1(1))=10$
$p= ( 2,3 )$ : $f_2(f_3(1))=11$
$p= ( 3,1 )$ : $f_3(f_1(1))=22$
$p= ( 3,2 )$ : $f_3(f_2(1))=26$

よって、 $26$ と出力します。

入力例 2Copy

Copy

出力例 2Copy

Copy

Score : $500$ points

Problem Statement

You are given $N$ linear functions $f_1, f_2, \ldots, f_N$ , where $f_i(x) = A_i x + B_i$ .

Find the maximum possible value of $f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots ))$ for a sequence $p = (p_1, p_2, \ldots, p_K)$ of $K$ distinct integers between $1$ and $N$ , inclusive.

Constraints

$1 \leq N \leq 2 \times 10^{5}$
$1 \leq K \leq \text{min}(N,10)$
$1 \leq A_i, B_i \leq 50$ $(1 \leq i \leq N)$
All input values are integers.

Input

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

 $N$   $K$ 
 $A_1$   $B_1$ 
 $A_2$   $B_2$ 
 $\vdots$ 
 $A_N$   $B_N$

Output

Print the answer as an integer.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Here are all possible $p$ and the corresponding values of $f_{p_1}(f_{p_2}(1))$ :

$p= ( 1,2 )$ : $f_1(f_2(1))=15$
$p= ( 1,3 )$ : $f_1(f_3(1))=15$
$p= ( 2,1 )$ : $f_2(f_1(1))=10$
$p= ( 2,3 )$ : $f_2(f_3(1))=11$
$p= ( 3,1 )$ : $f_3(f_1(1))=22$
$p= ( 3,2 )$ : $f_3(f_2(1))=26$

Therefore, print $26$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy