OpenKattis
POwarmup23 svår: svår DP
Problem B
Julklappsköp
Picture by
Trogain (cc-by-sa4.0)
Nu vill Allnäs maximera sina vänners glädje. Hon vill ge sina vänner presenter på ett sånt sätt, att summan av glädjen för varje vän (d.v.s. talen $a_{ij}$) blir maximal. Vilka julklappar ska hon köpa för att maximera summan av sina vänners glädje?
Indata
Den första raden innehåller två heltal $K$ (antal vänner) och $N$ (antal presenter).
De följande $K$ raderna innehåller $N$ heltal vardera. På den $i$:te raden är det $j$:te heltalet $0 \le a_{ij} \le 10^8$ – hur glad den $i$:te vännen blir om den får den $j$:te presenten.
Utdata
Du ska skriva ut ett heltal – den maximala summan av vännernas glädje.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
1 |
8 |
$K = 2, 1 \le N \le 5000$ |
|
2 |
15 |
$K = 2, 1 \le N \le 100\, 000$ |
|
3 |
30 |
$1 \le K \le 8, 1 \le N \le 100\, 000$ |
|
4 |
27 |
$1 \le K \le 14, 1 \le N \le 200$ |
|
5 |
20 |
$1 \le K \le 14, 1 \le N \le 100\, 000$ |
Förklaring av exempel 1
Om Allnäs köper present 3 till vän 1 och present 2 till vän 2 blir summan $a_{31} + a_{22} = 4 + 7 = 11$, vilket är det bästa som går.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 3 3 6 4 4 7 4 |
11 |
