Vasa sakupljac aura

Vasa – zberateľ - st

Vasa má 0 aury. Vase sa to nepáči. Preto sa rozhodol zbierať auru prechodom cez postupnosť. Formálne, pre danú postupnosť celých čísel b dĺžky k začína Vasa na indexe i = 1 s aurou a = 0 a koeficientom c = 1. Potom prechádza postupnosť a postupne zbiera auru prvkov tak, že si k svojej aure pripočíta hodnotu c · bᵢ. Po zozbieraní aury prvku i môže zvýšiť hodnotu koeficientu c o jeden. Prirodzene, Vasa chce maximalizovať výslednú auru po prechode celej postupnosti (táto hodnota môže byť aj záporná). Zároveň chce, aby po prechode celej postupnosti bola hodnota koeficientu c presne x. Daná je postupnosť p s n prvkami. Vypíšte auru, ktorú môže Vasa získať pre každú podpostupnosť b s dĺžkou presne k. Jednotlivé výpočty sú navzájom nezávislé.

Popis vstupu V prvom riadku sú dané tri celé čísla:
n – dĺžka postupnosti p,
k – dĺžka podpostupností, na ktorých Vasa zbiera auru,
x – konečná hodnota koeficientu c. V druhom riadku je n celých čísel. i-te z nich je pᵢ a predstavuje hodnotu i-teho prvku postupnosti p.

Popis výstupu Vypíšte n − k + 1 čísel – maximálnu hodnotu aury pre každú podpostupnosť dĺžky k postupnosti p.

Príklad 1 Vstup 5 3 2 1 -2 4 4 -5 Výstup 7 14 3 Vysvetlenie Existujú tri podpostupnosti dĺžky k = 3: • [1, -2, 4] – Vasa zvýši c z 1 na 2 po druhom prvku, výsledná aura je
1·b₁ + 1·b₂ + 2·b₃ = 1·1 − 1·2 + 2·4 = 7 • [-2, 4, 4] – zvýši c po prvom prvku, výsledná aura je
1·b₁ + 2·b₂ + 2·b₃ = −2 + 8 + 8 = 14 • [4, 4, -5] – c nezvýši, výsledná aura je
1·b₁ + 1·b₂ + 1·b₃ = 4 + 4 − 5 = 3

Príklad 2 Vstup 7 4 3 -10 2 2 -5 -4 5 7 Výstup -12 -9 4 23

Obmedzenia • 1 ≤ x ≤ k ≤ n ≤ 200 000 • |pᵢ| ≤ 10⁹ pre každé i Testy sú rozdelené do 6 skupín: • 10 bodov: n ≤ 20 • 10 bodov: pᵢ ≥ 0 • 15 bodov: n ≤ 300 • 15 bodov: n ≤ 3 000 • 20 bodov: x = 2 • 30 bodov: bez ďalších obmedzení