Liczba osob: 78
Liczba osob na 100 punktow: 53
Sredni wynik: 75.641
Wilcze doły
Limit pamięci: 128 MB
Król Bajtocji, Bajtazar III Zuchwały, planuje najazd na zamek wroga. Zamek jest z trzech stron otoczony niemożliwą do sforsowania fosą, więc Bajtazarowi pozostaje przypuścić atak na czwartą ścianę zamku. Sprawa nie jest jednak taka prosta, gdyż królewscy zwiadowcy donieśli o tym, że wzdłuż tej ściany wróg wykopał głębokie wilcze doły. Bajtazar chciałby zaatakować jak najdłuższy spójny fragment tej ściany. W tym celu będzie musiał zrównać z ziemią niektóre doły. Król postanowił, że część z nich przysypie piachem, a część przykryje Wielką Dechą.
Wzdłuż ściany wykopanych jest dołów. Król Bajtazar posiada
worków z piachem.
Do przysypania
-tego dołu potrzebne jest
takich worków.
Ponadto, Wielka Decha pozwala na przykrycie
sąsiednich dołów.
Pomóż Bajtazarowi znaleźć długość najdłuższego fragmentu ściany, który będzie mógł zaatakować, jeśli optymalnie wykorzysta worki z piachem i Wielką Dechę. Innymi słowy, oblicz, ile maksymalnie kolejnych dołów może zostać zrównanych z ziemią.
Wejście
Pierwszy wiersz standardowego wejścia zawiera trzy liczy całkowite ,
oraz
(
,
) pooddzielane pojedynczymi odstępami,
oznaczające odpowiednio liczbę dołów,
liczbę worków z piachem oraz długość Wielkiej Dechy.
Kolejny wiersz opisuje doły i zawiera ciąg liczb całkowitych
(
) pooddzielanych pojedynczymi odstępami;
oznacza liczbę worków potrzebnych do przysypania
-tego dołu.
W testach wartych łącznie punktów zachodzi dodatkowy warunek
.
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą długości najdłuższego spójnego fragmentu ściany, na który Bajtazar może przypuścić atak.
Przykład
Dla danych wejściowych:
9 7 2 3 4 1 9 4 1 7 1 3
poprawną odpowiedzią jest:
5
Wyjaśnienie do przykładu: Bajtazar może przysypać doły o numerach 2, 3 i 6 (zużywając do tego celu 6 spośród 7 posiadanych worków z piachem) oraz przykryć Wielką Dechą doły 4 i 5. W ten sposób król zrówna z ziemią pięć kolejnych dołów (o numerach od 2 do 6).
Testy "ocen":
- 1ocen:
,
,
, wszystkie
; można zrównać z ziemią wszystkie doły poza jednym;
- 2ocen:
,
,
, doły o parzystych numerach potrzebują dwóch worków z piachem, zaś doły o nieparzystych numerach potrzebują jednego worka.
Autor zadania: Jacek Tomasiewicz.
<Wyślij rozwiązanie> [0/100]