루미 알고리즘

#1416플래티넘Julklappsköp

PO 2017 결선코딩출제 Simon Lindholm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GruppPoängvärdeGränser
18K = 2, 1 ≤ N ≤ 5000
215K = 2, 1 ≤ N ≤ 100000
3301 ≤ K ≤ 8, 1 ≤ N ≤ 100000
4271 ≤ K ≤ 14, 1 ≤ N ≤ 200
5201 ≤ 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

출처 표기

출처: Programmeringsolympiaden 2017년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.