Najljepši put (Bicikl)

Opis zadatka:

Džil voli da vozi svoj bicikl, ali ona ponekad koristi odličan sistem javnog prevoza u svom rodnom gradu da bi prešla određene dionice. Ona ima rasklapajući bicikl koji može ponijeti sa sobom kada se vozi u autobusu. Kada autobus dođe do lijepih dijelova grada, Džil izlazi iz autobusa i vozi svoj bicikl. Ona prati autobusku liniju na biciklu dok ne dođe do svog odredišta ili ne dođe do dijela grada koji joj nije ugodan. U tom slučaju ponovo ulazi u autobus da bi završila svoje putovanje.

Tokom godina iskustva, Džil je ocijenila svaku ulicu na cjelobrojnoj skali "ljepote". Pozitivne vrijednosti predstavljaju ulice koje Džil voli; negativne vrijednosti se koriste za ulice koje Džil ne voli. Ne postoje vrijednosti nula. Džil planira svoj put na taj način da bira ulice kojima će se voziti biciklom, prije nego što se ponovo ukrca na autobus, tako da suma "ljepota" ulica bude maksimalna. To znači da će se ona voziti ulicama koje ne voli pod uslovom da će ostatak puta uključivati ulice koje će to kompenzirati. Postoji mogućnost da nijedan dio puta nije pogodan za vožnju na biciklu, tako da će se ona voziti cijelo vrijeme u autobusu. Također, postoji mogućnost da je čitav put lijep, tako da ona neće nikako ni uzimati autobus.

Pošto postoje mnoge autobuske linije, sa mnogo stanica na kojima Džil može ući odnosno izaći iz autobusa, potrebna joj je pomoć računara da odredi najbolji dio za vožnju biciklom za svaku autobusku liniju.

Izvršni program treba da se nalazi u direktoriju C:\BHOI2003 pod imenom BICIKL.EXE.

Ulazna datoteka:

Ulazni podaci se nalaze u tekstualnoj datoteci BICIKL.IN, u kojoj se nalaze informacije o autobuskoj liniji. Prva linija u datoteci sadrži cijeli broj S (2 <= S <= 20000) koji predstavlja broj autobuskih stanica na liniji. Nakon toga slijedi S-1 linija, gdje svaka linija I (1 <= I <=S) sadrži cijeli broj N_I koji predstavlja ocjenu ljepote za ulicu izmedu stanica I i I+1.

Izlazna datoteka:

Izlazni podaci se pišu u tekstualnu datoteku BICIKL.OUT koja treba da sadrži samo jednu liniju. Vaš program treba da odredi početnu autobusku stanicu I i krajnju autobusku stanicu J koje identificiraju segment puta koji daje maksimalnu sumu "ljepote"

M = N_I + N_I+1 + ... + N_J-1

Ako postoje dva segmenta sa maksimalnom vrijednošću ljepote, potrebno je izabrati segment sa najdužom vožnjom biciklom (tj. za koji je razlika J-I najveća). Ako postoje segmenti sa istom maksimalnom ljepotom, i iste dužine, potrebno je izabrati onaj koji počinje ranije (tj. za koji je I najmanje). Ispis u izlaznu datoteku treba da bude u sljedećoj formi:

Najljepsi dio puta je izmedju stanica I i J

Međutim, ako maksimalna suma nije pozitivna, program treba da ispiše:

Put nema lijepih dijelova

Vremensko ograničenje:

Za svaki testni primjer program treba da ponudi rješenje za najviše 10 sekundi.

Primjeri:

BICIKL.IN
3
-1
6
BICIKL.OUT
Najljepsi dio puta je izmedju stanica 2 i 3
BICIKL.IN
10
4
-5
4
-3
4
4
-4
4
-5
BICIKL.OUT
Najljepsi dio puta je izmedju stanica 3 i 9
BICIKL.IN
4
-2
-3
-4
BICIKL.OUT
Put nema lijepih dijelova

[Testni podaci] [Rješenje (Pascal)] [Rješenje (C++)]