Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
C. Оновчтой нийлбэр
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Одоо бид өөр нэгэн цувааны бодлого бодох гэж байна. Танд эерэг бүхэл тоо $len$ болон $n$ ширхэг бүхэл тоо $a_{1}$, $a_{2}$, ..., $a_{n}$-уудаас тогтох $a$ цуваа өгөгджээ. Өгөгдсөн цувааны 2 шинж чанарыг танилцуулъя.
$len$ урттай $i$ байрлалаас эхлэх цувааны дурын завсрыг авч үзье.
утга нь сонгогдсон завсрын модулар нийлбэр юм. Өөрөөр хэлбэл, модулар нийлбэр гэдэг нь $len$ урттай сонгогдсон завсрын бүхэл тоонуудын нийлбэрийн абсолют утга юм.
утга нь цувааны оновчтой нийлбэр юм. Өөрөөр хэлбэл, цувааны оновчтой нийлбэр гэдэг нь цувааны $len$ урттай янз бүрийн завсруудын бүх модулар нийлбэрүүдийн хамгийн их нь юм.
Таны даалгавар бол өгөгдсөн $a$ цувааны оновчтой нийлбэрийг тооцоолох юм. Гэсэн хэдий ч, таныг тооцохоос өмнө танд $k$-аас ихгүй дараах хэлбэртэй дараалсан үйлдлүүдийг уг цуваанд хийхийг зөвшөөрсөн: нэг үйлдэл гэдэг нь $a_{i}$ цуваанаас дурын байдлаар нэг тоог сонгоод уг тоогоо -1 ээр үржүүлэх юм. Өөрөөр хэлбэл, $k$-аас ихгүй удаа та цуваанаас дурын байдлаар $a_{i}$ тоог сонгоод үүнийг $-a_{i}$-аар солих юм. Цувааны тоо бүр нь дурын тооны удаа сонгогдож болно.
Таны даалгавар бол хамгийн ихдээ $k$ удаа дээр дүрслэгдсэн үйлдлүүд хийгдсэний дараах цувааны боломжит хамгийн их оновчтой нийлбэрийг тооцоолох юм.
Оролт
Эхний мөрөнд 2 бүхэл тоо $n$, $len$ ($1 ≤ len ≤ n ≤ 10^{5}$) өгөгдөнө -- эдгээр нь харгалзан цувааны элементийн тоо болон цувааны сонгогдсон дэд завсрын уртыг илэрхийлнэ.
2-дахь мөрөнд $n$ бүхэл тоо $a_{1}$, $a_{2}$, ..., $a_{n}$ $(|a_{i}| ≤ 10^{9})$-уудаас тогтох дараалал өгөгдөнө -- эдгээр нь анхны цувааг илэрхийлнэ.
3-дахь мөрөнд ганц бүхэл тоо $k$ ($0 ≤ k ≤ n$) өгөгдөнө -- энэ нь зөвшөөрөгдсөн үйлдлийн хамгийн их тоог илэрхийлнэ.
Мөрөнд өгөгдөх бүх тоонууд нь зайгаар тусгаарлагдсан байна.
Гаралт
Ганц мөрөнд $k$-аас ихгүй зөвшөөрөгдсөн үйлдлийг хийсний дараах боломжит хамгийн их оновчтой нийлбэрийг хэвлэнэ.
С++ дээр 64-битийн бүхэл тоонуудыг унших болон бичихдээ %lld тодорхойлогчийг битгий ашиглана уу. cin, cout streams эсвэл %I64d тодорхойлогчийг ашиглахыг илүүд үзнэ үү.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
5 3 0 -2 3 -5 1 2
Гаралт
10
Оролт
5 2 1 -3 -10 4 1 3
Гаралт
14
Оролт
3 3 -2 -5 4 1
Гаралт
11