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]