스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
Picture by Trogain (https://commons.wikimedia.org/wiki/File:Christmas_presents_and_a_tree.jpg) (cc-by-sa4.0)
Snälla Allnäs ska köpa en julklapp vardera till sina K vänner (trots att det är februari – Allnäs tror på att ha god marginal). Butiken hon är i har exakt ett exemplar av varje vara. Det finns totalt N varor. Allnäs känner sina vänner mycket bra – hon vet exakt vem som gillar vad och hur mycket. Hon har skrivit ner en lista med alla a_ij tal, talen som säger hur mycket vän i gillar present j.
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 ≤ a_ij ≤ 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 ≤ N ≤ 5000 |
| 2 | 15 | K = 2, 1 ≤ N ≤ 100000 |
| 3 | 30 | 1 ≤ K ≤ 8, 1 ≤ N ≤ 100000 |
| 4 | 27 | 1 ≤ K ≤ 14, 1 ≤ N ≤ 200 |
| 5 | 20 | 1 ≤ K ≤ 14, 1 ≤ N ≤ 100000 |
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.
예제
예제 1
2 3 3 6 4 4 7 4
11