루미 알고리즘

#1500골드TV-tittande

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

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

Problem

Bobs vänner älskar TV-serier och brukar diskutera dem på sina födelsedagskalas. Bob känner sig ofta utfryst för att han inte har kollat på samma serier som dem.

Bob är bjuden på kalas vissa dagar och tänker gå på alla dessa. Han vet vilka TV-serier som kommer diskuteras under varje kalas, och vill ha sett klart de serierna för att kunna diskutera dem med sina vänner. Bob vill inte titta på TV i mer än tio timmar per dag, och han har inte tid att titta på TV på samma dag som han är på ett kalas.

Han kan när som helst pausa en TV-serie och fortsätta titta på den någon annan gång, men när han är på ett kalas där serien diskuteras måste han ha sett klart hela. Kan Bob lyckas med det?

Indata

På första raden finns de två heltalen n och k (1 ≤ n,k ≤ 2 · 10^5), antalet kalas och antalet TV-serier som finns. TV-serierna är numrerade från 1 till k.

På nästa rad finns k heltal, där det i:te talet är längden av TV-serie nummer i mätt i timmar. Ingen serie är längre än 10^6 timmar.

De följande n raderna beskriver kalasen i ordning. Rad i börjar med två heltal 1 ≤ d_i ≤ 2 · 10^5 och c_i ≥ 1, vilken dag kalaset är och antalet TV-serier som kommer att diskuteras. Sedan följer c_i olika heltal på samma rad, de TV-serier som kommer diskuteras på kalaset. Summan av alla c_i är inte större än 2 · 10^5.

Bob är inte bjuden till mer än ett kalas någon dag. Det är nu morgon dag 0 och Bob ska alltså inte på kalas idag.

Utdata

Skriv ut Ja om det är möjligt att se klart TV-serierna i tid till evenemangen där de diskuteras. Skriv ut Nej om det inte är möjligt.

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
140n ≤ 50, k ≤ 50
220n ≤ 3000, k ≤ 3000
340Inga ytterligare begränsningar.

Förklaring av exempelfall 1

Första kalaset är om två dagar, och där ska den 20 timmar långa TV-serien diskuteras. Eftersom Bob tänker titta på TV i tio timmar per dag hinner han som tur är precis se den i tid. Sedan får han en ledig dag till nästa kalas så att han precis hinner se serie 3 och 4 på fem timmar var. På den femte dagen räcker det att Bob tittar på serie 1 eftersom han redan har sett serie 2.

예제

예제 1

입력
3 4
3 20 5 5
2 1 2
4 2 3 4
6 2 1 2
출력
Ja

예제 2

입력
2 4
7 3 8 3
1 2 1 2
2 3 2 3 4
출력
Nej

예제 3

입력
3 5
3 10 4 8 15
2 2 1 3
4 1 2
7 3 5 4 2
출력
Ja

출처 표기

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