Bola už hlboká noc, keď sa Jožko prebudil zo spánku. Sníval sa mu veľmi živý sen, z oblohy padali asteroidy, plné prerôznych krásnych kameňov1. Nadšený, úplne zabudol, že to bol iba sen, vyskočil z postele a vybehol von. Nočná obloha bola jasná, hviezdy svietili… a, čo to? Zreteľne padala hviezda. Jožko, ešte v papučiach, sa za ňou rozbehol, keď sa v tej tme potkol a spadol. Pozrel sa na zem a, čo nevidí? Kameň! To nemôže byť náhoda. Ako sa zahľadel zas na oblohu všimol si ďalší, zreteľne padajúci asteroid. Už nečakal a rozbehol sa za ním. V svetle mesiaca uvidel dopadnutý kameň, ešte krajší ako predchádzajúci, ale ako sa poň načahoval, rozplynul sa mu pred očami.
Zvláštne, pomyslel si Jožko. Skúšal zabehnúť ešte za pár kameňmi, ale polovicu nestihol, rozplynuli sa. Keďže je Jožko zvedavý chlapec, hneď sa rozhodol vyskúmať, ako to je s tými kameňmi. Napriek tomu, že bola hlboká noc, hackol sa do satelitných dát a vypočítal kedy, kde a aký2 kameň dopadne. Ostávajú posledné hodiny noci a Jožko sa zas vyberá na lov kameňov. Zaujímalo by ho, s akým úlovkom vie skončiť.
Úloha
Svet si vieme predstaviť ako priamku.
Na zem postupne spadne \(n\) (\(n \leq 500\,000\)) kameňov, \(i\)-tý z nich v čase \(t_i\), na mieste \(x_i\) a má hodnotu \(v_i\). Dva kamene môžu spadnúť na rovnaké miesto, alebo v rovnakom čase (nie však obe naraz). Pre jednoduchosť všetky časy sú v celých sekundách a súradnice v celých metroch. Kamene ostanú na mieste presne sekundu a potom sa rozplynú.
Jožko vie bežať jeden meter za sekundu. Na začiatku (v čase nula) stojí na súradnici \(p\). V prípade, že bude zbierať kamene optimálne, aký najväčší súčet hodnôt, ktorý vie získať?
Formát vstupu
Na prvom riadku sú dve medzerami oddelené čísla: \(n\), počet kameňov a \(p\), Jožkovú začiatočnú pozíciu.
V druhom riadku je \(n\) medzerami oddelených čísiel, \(t_1\) až \(t_n\), časy dopadu jednotlivých kameňov.
V treťom riadku je \(n\) medzerami oddelených čísiel, \(x_1\) až \(x_n\), miesta dopadu jednotlivých kameňov.
A na štvrtom riadku je \(n\) medzerami oddelených čísiel, \(v_1\) až \(v_n\) - hodnoty jednotlivých kameňov.
Je zaručené že dva kamene nedopadnú na rovnaké miesto v rovnaký čas.
Formát výstupu
Vypíšte dva riadky: na prvom, dve medzerami oddelené čísla - počet kameňov, ktoré Jožko v optimálnom prípade pozbiera a súčet ich hodnôt.
Na druhom riadku vypíšte čísla kameňov (číslo kameňa je jeho pozícia vo vstupe, číslované od nuly) ktoré má Jožko pozbierať, oddelené medzerou.
Ak existuje viac riešení, vypíšte ľubovoľné z nich.
Hodnotenie
Vaše programy budeme testovať na štyroch skupinách testovacích vstupov. Pre jednotlivé skupiny budú platiť nasledujúce obmedzenia:
Skupina | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1\leq n\leq\) | \(5\,000\) | \(100\,000\) | \(200\,000\) | \(500\,000\) |
\(0\leq p, x_i, t_i\leq\) | \(10^9\) | \(5\,000\) | \(250\,000\) | \(10^9\) |
Vo všetkých vstupoch, \(0 < v_i \leq 10^9\)
Príklad
Input:
3 0
60 40 50
0 35 40
3 1 1
Output:
1 3
0
Input:
6 3
7 3 5 3 4 8
10 0 2 4 5 4
20 3 9 5 7 8
Output:
3 22
2 5 3
Jožkovi sa oplatí najskôr vziať kameň, ktorý spadne v tretej sekunde na mieste jedna, potom prebehnúť na doľava na kameň s hodnotou 9. Napokon sa prejde dva metre doprava a zoberie kameň s hodnotou 8. Takto získa kamene s hodnotou 22. Ak by sa rozhodol zobrať kameň s hodnotou 20, potom nevie zobrať iný kameň.
Input:
3 0
0 1 2
1 2 3
100 100 100
Output:
0 0
Jožko žiaľ nestihne dobehnúť pre žiadny z kameňov.
Kamene sú tu s nami už od doby KAMENnej a podnietili náš rozvoj v oblasti života. Bez nich by sme tu neboli, ale aj tak mám pocit, že nedostavajú také uznanie ako si zaslúžia. Kamene sú v mnohých ohľadoch (napr. tvrdosť, vytrvalosť, dĺžka života, zmysel pre humor, chuť, …) omnoho nadradenejšie ako my.↩︎
niektoré kamene sú lepšie ako iné↩︎
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.