| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 | 2048 MB | 11 | 2 | 1 | 10.000% |
Na brojevnom pravcu nalazi se $N$ zečeva, $i$-ti zec se nalazi na poziciji $x_i$ te na početku ima $p_i$ energije. Svake sekunde događa se sljedeće: ako svi zečevi imaju bar jednu jedinicu energije, skaču za jedno mjesto u desno te potroše jednu jedinicu energije. Ako barem jedan zec ima nula energije, svi prestaju skakati zauvijek.
Mrkve. Mrkve su također na istom brojevnom pravcu, $i$-ta mrkva se nalazi na poziciji $y_i$ i teška je $t_i$ kilograma. Kad zec dođe na poziciju gdje se nalazi mrkva, može pojesti $a$ kilograma te mrkve, gdje je a cijeli broj između 0ドル$ i težine te mrkve. Nakon toga tom zecu se poveća energija za $a,ドル a težina te mrkve se smanji za $a$ kilograma.
Odredite koliko najviše sekundi zečevi mogu skakati, ukoliko na optimalan način jedu mrkve.
U prvom retku su prirodni brojevi $N$ i $M,ドル broj zečeva i broj mrkvi.
U sljedećih $N$ redaka nalaze se po dva broja. U $i$-tom od tih redaka nalaze se brojevi $x_i$ i $p_i$ , početna pozicija i energija $i$-tog zeca.
U sljedećih $M$ redaka nalaze se po dva broja. U $i$-tom od tih redaka nalaze se brojevi $y_i$ i $t_i,ドル pozicija i početna težina $i$-te mrkve.
Ispišite koliko najviše sekundi zečevi mogu skakati.
U svim podzadacima vrijedi 1ドル ≤ N, M ≤ 10^5,ドル 0ドル ≤ x_i , y_i ≤ 10^9,ドル 0ドル ≤ p_i , t_i ≤ 10^9$. Nijedna dva zeca te nijedne dvije mrkve nisu na istoj poziciji. Nijedan zec nije na istoj početnoj pozicija kao neka mrkva.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 9 | $N = 1$ |
| 2 | 12 | $M = 1$ |
| 3 | 26 | $N, M ≤ 1000$ |
| 4 | 34 | $N, M ≤ 50000$ |
| 5 | 19 | Nema dodatnih ograničenja. |
3 5 2 4 7 3 9 5 3 2 8 1 10 2 6 3 1 3
5
5 1 2 6 3 7 5 4 1 10 7 2 8 27
11
Pojašnjenje prvog probnog primjera:
Nakon prva tri skoka zečevi imaju energije redom 1ドル,ドル 0ドル$ i 2ドル$. Drugi zec se sada nalazi na poziciji na kojoj je mrkva težine 2ドル$ pa ju može cijelu pojesti, čime njegova energija postaje 2ドル$. Zečevi sada opet mogu napraviti jedan skok, nakon čega im energije postaju 0ドル,ドル 1ドル$ i 1ドル$. Prvi zec se sada nalazi na poziciji 6ドル$ na kojoj je mrkva težine 3ドル$. Nakon jedenja mrkve zečevi imaju težine 3ドル,ドル 1ドル$ i 1ドル$ pa mogu napraviti još jedan skok. Ukupan broj napravljenih skokova je pet. Moguće je pokazati da je nemoguće postići da zečevi naprave šest skokova.