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. ### 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