루미 알고리즘

#1475골드Matbeställning

PO 2019 온라인 예선코딩출제 Fredrik Hernqvist스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Anthony och hans n vänner är på restaurang och ska beställa mat. Menyn har m rätter, och alla vännerna har från början valt rätter som de vill ha. Anthony blir dock gladare ju fler olika rätter sällskapet beställer, så att han får se mer av vad restaurangen har att erbjuda. Han kan till och med tänka sig att betala för vännernas mat för att höja antalet olika beställda rätter.

Idag vill Anthony att vännerna ska beställa minst k olika rätter. Han kan få en vän att byta beställning till en dyrare rätt genom att betala mellanskillnaden mellan kostnaden för vännens ursprungliga val och den dyrare rätten (men varje person beställer fortfarande bara en sak). Han kan göra så många sådana byten som han vill.

Givet antalet rätter, deras kostnader, och vännernas ursprungliga beställningar, vad är det minsta Anthony behöver betala för att kunna se till att vännerna beställer minst k olika rätter?

Indata

Den första raden innehåller tre heltal n, m och k (1 ≤ n, m ≤ 2 · 10^5, 1 ≤ k ≤ min(n, m)), antalet vänner, antalet rätter och det önskade antalet unika beställningar. Därefter kommer en rad med n heltal x_1 … x_n, där x_i (1 ≤ x_i ≤ m) är den rätt som vän i från början vill köpa. Därefter kommer en rad med m heltal c_1 … c_m, där c_i (1 ≤ c_i ≤ 10^9) är kostnaden för rätt i.

Utdata

Ett heltal, det minsta beloppet som Anthony behöver betala för att vännerna ska beställa minst k olika rätter. Om det är omöjligt, skriv ut -1. Notera att svaret inte nödvändigtvis får plats i ett 32-bitars heltal.

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
110Från början vill alla köpa samma rätt.
220k = n
316n, m ≤ 15
423c_i = i för alla 1 ≤ i ≤ m, d.v.s. rätternas priser är 1, 2, 3, …, m
531Inga restriktioner

Förklaring av exempelfall

I det första exempelfallet kan Anthony betala 2 kronor för att vän 1 ska byta från den första till den tredje rätten. Efter det beställs 3 unika rätter: rätt 1, rätt 2 och rätt 3.

I det andra exempelfallet finns det två rätter som båda kostar 10 kronor, och båda vännerna har valt den första rätten. Då det inte finns någon dyrare rätt än den första kan inte Anthony göra något för att ändra vännernas val, och kan aldrig uppnå 2 unika rätter. Svaret blir då -1.

I det tredje exempelfallet vill vännerna redan ha två olika rätter, så Anthony behöver inte betala någonting.

I det sista exempelfallet vill Anthony se till att alla 8 vänner beställer olika rätter. Det billigaste alternativet här är att betala för att vän 3, 4, 7 och 8 ska uppgradera till en av 1000000000-kronorsrätterna. Totalt kostar det 3999999990 kronor.

예제

예제 1

입력
3 4 3
1 1 2
1 2 3 4
출력
2

예제 2

입력
2 2 2
1 1
10 10
출력
-1

예제 3

입력
2 2 1
1 2
10 10
출력
0

예제 4

입력
8 8 8
1 2 3 4 1 2 3 4
1 2 3 4 1000000000 1000000000 1000000000 1000000000
출력
3999999990

출처 표기

출처: Programmeringsolympiaden 2019년 온라인 예선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.