| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 2 | 2 | 1 | 100.000% |
Zigmas dirba rūbinėje, kur įnoringi žmonės patys pasikabina rūbus, bet paskui lieka nepatenktinti vieta, kurioje juos pakabino.
Rūbinėje yra tiesi rūbų kabykla, kur N žmonių pakabino po vieną rūbą. Visi rūbai kabo taškuose ai, kurių koordinatės yra sveikieji skaičiai. Viename taške kabo ne daugiau kaip vienas rūbas. Kiekvieno rūbo savininkas nori perstumti savo rūbą į tašką, kurio koordinatė bi, ir jo nepasitenkinimas lygus jo rūbo atstumui iki norimo taško.
Zigmas nori kuo labiau sumažinti savininkų nepasitenkinimą perstumdydamas rūbus. Jam neleista nukabinti rūbų, taigi rūbai negali susikeisti vietomis, bet leidžiama sustumti kelis rūbus taip arti vienas kito, kad jie turėtų tą pačią koordinatę.
Suskaičiuokite, kokia gali būti mažiausia nepasitenkinimų suma perstumdžius rūbus.
Pirmoje eilutėje pateikti du tarpais atskirti sveiki skaičiai – rūbų skaičius N ir kabyklos ilgis L.
Antroje eilutėje pateikta N tarpais atskirtų sveikųjų skaičių ai, žyminčių pradines rūbų koordinates.
Trečioje eilutėje pateikta N tarpais atskirtų sveikųjų skaičių bi, žyminčių koordinates, kuriose savininkai nori, kad atsidurtų jų rūbai.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | N, L ≤ 8 |
| 2 | 8 | |ai − bi| ≤ 1 |
| 3 | 17 | N, L ≤ 200 |
| 4 | 13 | N ≤ 5 000 |
| 5 | 50 | Papildomų ribojimų nėra |
4 6 5 1 2 4 4 5 3 2
3
Jei pirmą rūbą nustumtume į koordinatę 4, o likusius rūbus sustumsime į koordinatę 3, tai pirmo ir trečio rūbo savininkų nepasitenkinimas bus 0, antro 2, o ketvirto 1.
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2020/2021 > National Round (2) > 10-12 Classes 3번