Codeforces Round #716 (Div. 2)
01:44:23 |
Codeforces Round #717 (Div. 2)
3 өдрийн дараа |
Codeforces Round #718 (Div. 1)
5 өдрийн дараа |
Codeforces Round #718 (Div. 2)
5 өдрийн дараа |
Codeforces Global Round 14
14 өдрийн дараа |
B. Шоргоолж Хүн
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Скотт Ланг Даррен Кроссын эсрэг дайн зарлажээ. Танхимд $n$ ширхэг сандал байгаа бөгөөд зүүнээс баруун уруу $1, 2, ..., n$ дугаарлагджээ. $i$ дэхь сандлын координат нь $x_{i}$. Скот $s$ дугаартай сандал дээр байгаа бөгөөд Кросс $e$ дугаартай сандал дээр байгаа. Скотт бүх сандал уруу шууд үсэрч чадна (зөвхөн зэрэгцээ хажуу талын сандалууд уруу биш). Тэрээр байгаа сандал $s$ дээрээсээ бүх бусад сандал дээр яг нэг удаа буун эцэст нь Кроссын байгаа $e$ сандал дээр буухыг хүсэж байгаа.
Бид бүгдийн мэдэхээр Скотт жижгэрч болон томорч чадна (томрохдоо зөвхөн өөрийн хэвийн байдал уруу томорно), тиймээс аль ч мөчид тэрээр жижиг эсвэл том (хэвийн) хэмжээтэй байж чадна. Гэвч тэрээр зөвхөн сандал дээр байхдаа жижгэрч эсвэл томорч чадна (сандал уруу үсэрч байх үедээ чадахгүй). Үүнээс гадна, сандалнаас сандал уруу үсэрэхэд цаг шаардана. Харин хэмжээгээ өөрчлөхөд шаардахгүй. $i$ сандалнаас $j$ сандал уруу үсэрхэд $|x_{i} - x_{j}|$ секунд шаардана. Бас сандалнаас үсрэх болон сандал дээр буух нь нэмэлт хугацаа шаардана.
Хэрвээ Скотт өөрийн зүүн талын сандал уруу үсэрвэл тэрээр жижиг байх шаардлагатай, харин баруун талын сандал уруу үсэрвэл тэрээр том (хэвийн) байх шаардлагатай.
$i$ дэхь сандалнаас үсрэхэд:
- $c_{i}$ нэмэлт секунд хэрвээ жижиг бол,
- $d_{i}$ нэмэлт секунд хэрвээ том бол.
$i$ дэхь сандал дээр буухад:
- $b_{i}$ нэмэлт секунд хэрвээ жижиг бол,
- $a_{i}$ нэмэлт секунд хэрвээ том бол.
Энгийнээр, $i$ дэхь сандалнаас $j$ дэхь сандал уруу үсэрвэл нийт:
- $|x_{i} - x_{j}| + c_{i} + b_{j}$ секунд хэрвээ $j < i$.
- $|x_{i} - x_{j}| + d_{i} + a_{j}$ секунд хэрвээ $j > i$.
Утгууд $x$, $a$, $b$, $c$, $d$-ыг өгөх бөгөөд Скотт сандал болгон дээр яг нэг удаа буун Кросс дээр очих хамгийн бага хугацааг ол.
Оролт
Эхний мөрөнд сандалны тоо, Скоттын эхлэл болон төгсгөлийн байрлалууд болох 3-н бүхэл тоонууд $n$, $s$, $e$ ($2 ≤ n ≤ 5000, 1 ≤ s, e ≤ n, s ≠ e$) өгөгдөнө.
2 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $x_{1}, x_{2}, ..., x_{n}$ ($1 ≤ x_{1} < x_{2} < ... < x_{n} ≤ 10^{9}$) өгөгдөнө.
3 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{1}, a_{2}, ..., a_{n} ≤ 10^{9}$) өгөгдөнө.
4 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $b_{1}, b_{2}, ..., b_{n}$ ($1 ≤ b_{1}, b_{2}, ..., b_{n} ≤ 10^{9}$) өгөгдөнө.
5 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $c_{1}, c_{2}, ..., c_{n}$ ($1 ≤ c_{1}, c_{2}, ..., c_{n} ≤ 10^{9}$) өгөгдөнө.
6 дахь мөрөнд $n$ ширхэг бүхэл тоонууд $d_{1}, d_{2}, ..., d_{n}$ ($1 ≤ d_{1}, d_{2}, ..., d_{n} ≤ 10^{9}$) өгөгдөнө.
Гаралт
Скотт бүх сандал дээр яг нэг удаа буун Кроссын байгаа сандал дээр очих хамгийн бага хугацааг олж хэвлэнэ үү.
Орчуулсан: Энхлут
Жишээ тэстүүд
Оролт
7 4 3 8 11 12 16 17 18 20 17 16 20 2 20 5 13 17 8 8 16 12 15 13 12 4 16 4 15 7 6 8 14 2 11 17 12 8
Гаралт
139
Тэмдэглэл
Жишээнд хамгийн тохиромжтой хариулт нь . Зарцуулагдсан нийт хугацаа $17 + 24 + 23 + 20 + 33 + 22 = 139$.