시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 20 | 7 | 7 | 50.000% |
W bajtockich górach wybudowano tarasy widokowe połączone za pomocą wind. Z tarasu położonego niżej można wjechać na taras sąsiedni, położony wyżej, za tyle kredytek ile wynosi różnica pomiędzy wysokościami tarasów. Z tarasu położonego wyżej na taras położony niżej zjeżdża się za darmo. Tarasy połączone są w łańcuch widokowy, w którym z pierwszego tarasu można dostać się tylko na drugi, z drugiego na pierwszy i trzeci, itd. Policz jaka jest największa liczba różnych tarasów, które bezpośrednio (czyli bez zjeżdżania z tarasu na ziemię) może odwiedzić turysta posiadający tylko k kredytek. Za wjazd na taras, od którego zacznie swoją wędrówkę, turysta nic nie płaci.
W pierwszym wierszu podane są dwie liczby całkowite n, k (1 ≤ n ≤ 20 000, 0 ≤ k ≤ 20 000), oddzielone pojedynczym odstępem. Liczba tarasów to n, a k to liczba kredytek, którymi dysponuje turysta. W kolejnych n wierszach podane są wysokości kolejnych tarasów: h1, h2, ..., hn. Każde hi spełnia nierówności: 1 ≤ hi ≤ 10 000.
Program powinien wypisać tylko jedną liczbę, równą największej liczbie tarasów, które może odwiedzić turysta za k kredytek.
5 1 4 2 1 2 4
4
Contest > Algorithmic Engagements > PA 2002.11 2-2번