Ribiči

Osnovne informacije

Omejitve
  • Čas: 10 s
  • Spomin: 128 MB
Avtor:
  • Nino Bašić
  • UPM 2017

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Prije jutra ribari se bude,
more zna njih, more zna te ljude.
Prije jutra u zoru
s galebima na moru
na poštama sunce čekaju.
— Vinko Coce, Ribari

Ribič Vinko je dobil visokotehnološki sonar, s katerim je natančno določil število rib v Piranskem zalivu. Ribe v Piranskem zalivu se vedejo nekoliko nenavadno, saj vsaka riba plava vedno v horizontalni smeri na svoji priljubljeni globini in nikoli v vertikalni smeri (tj. ne spreminja globine). Sonar je po dolgotrajnem skeniranju vrnil seznam števil r_1, r_2, \ldots, r_N. Število r_i je število rib, ki se nahajajo na globini i.

Vinko bo ribe lovil v K zaporednih dnevih. Ribolov poteka tako, da na začetku dneva (še preden vzide sonce) na svojo barko montira mrežo, ki bo potopljena do globine g. Njegova mreža je velikosti D, kar pomeni, da z njo ulovi ribe, ki se nahajajo na globinah g, g + 1, \ldots, g + D - 1. Po sončnem vzhodu Vinko pluje po Piranskem zalivu, dokler ne polovi čisto vseh rib, ki jih pri danem g sploh lahko polovi. Globino mreže lahko spremeni samo pred začetkom naslednjega dneva, nikoli pa med samo plovbo.

Ribiški maraton bo trajal K dni. V tem času ne bo prišlo do nastanka novih rib. Znano je, da ribe tudi ponoči ne plavajo v vertikalni smeri. Kakšno je največje število rib, ki jih Vinko lahko ulovi?

Vhodni podatki

V prvi vrstici se nahajajo tri cela števila, ki so ločena s presledki: število različnih globin N, velikost mreže D in dolžina ribiškega maratona K (v dneh). Druga vrstica vsebuje N s presledki ločenih celih števil r_1, r_2, \ldots, r_N. Število r_i je število rib na globini i.

Omejitve vhodnih podatkov

  • 1 \leq D \leq N \leq 100\,000
  • 1 \leq K \leq 50
  • 0 \leq r_i \leq 10\,000

Izhodni podatki

Izpišite eno samo število – največje število rib, ki jih Vinko lahko ulovi.

Primer

Vhod

10 3 2
7 1 2 1 3 5 4 0 1 2

Izhod

22

Komentar

Prvi dan Vinko nastavi mrežo na g = 1 in ulovi vse ribe na globinah 1, 2 in 3, kar znese r_1 + r_2 + r_3 = 7 + 1 + 2 = 10 rib. Drugi dan Vinko nastavi mrežo na g = 5 in tako ulovi vse ribe na globinah 5, 6 in 7, kar znese r_5 + r_6 + r_7 = 3 + 5 + 4 = 12 rib. V obeh dneh skupaj torej ulovi 10 + 12 = 22 rib.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task