e-olymp
Məsələlər

Dağ turizmi

Dağ turizmi

Olimpiya planetində aktiv turizm klubu müştərilərə şəfalı dağ silsiləsi boyunca marşrutlar təklif etməyi qərara aldı. Dağ silsiləsi kifayət qədər uzun idi və birdən-birə onu səyahət etmək çətindir, ona görə də klubda bu marşrutlardan məhdud uzunluqlu ən cəlbedici olanını axtarmağı qərara aldılar. Sosial tədqiqatların yekunlarına görə turistlər daha geniş sahəni görmək sayəsində və hündürlük hissindən alınan eyforiyaya görə digərlərinə nisbətən mümkün qədər böyük aralıqda daha hündür yerlərdə gəzməyi sevirlər.

prb221

Məsələni sadələşdirmək üçün dağ silsiləsini bir metrlik hissələrə böldülər və onların hər birinin dəniz səviyyəsindən orta hündürlüyünü müəyyənləşdirdilər.

Hər bir belə dağ silsiləsi parçasının cəlbediciliyinin ədədi qiyməti onun sağ və solundakı və ondan ciddi hündür olmayan qonşu parçalarının cəmi sayına bərabərdir. Parçanın özü bu cəmə daxil deyil. Marşrutun cəlbediciliyi ona daxil olan bir metrlik dağ silsiləsi hissələrinin cəlbediciliklərinin cəmi kimi hesablanır. Marşrutun uzunluğu T metrdən çox olmamalıdır. Marşrutun istiqaməti heç bir əhəmiyyət kəsb etmir, belə ki, istiqamət marşrutun cəlbediciliyini dəyişmir. Marşrut dağ silsiləsinin istənilən hissəsindən başlaya bilər. Marşrutda kəsilmələr ola bilməz, başqa sözlə, marşruta dağ silsiləsinin yalnız ardıcıl hissələrini daxil etmək olar.

Tapşırıq: Dağ silsiləsinin hər bir metrlik parçasının dəniz səviyyəsindən hündürlüyü haqqında informasiyaya görə uzunluğu T metrdən çox olmayan ən cəlbedici marşrutun uzunluğunu hesablamaq üçün proqram yazın.

Giriş verilənləri

Giriş faylının birinci sətrində iki tam ədəd verilir: N - bütün dağ silsiləsinin metrlə verilmiş uzunluğu və marşrutun uzunluğuna qoyulan T (1 ≤ T ≤ N ≤ 100 000) məhdudiyyəti. İkinci sətirdə N sayda 1-dən 106-dək tam ədəd - ardıcıl birmetrlik parçaların hündürlüyü yerləşir.

Çıxış verilənləri

Çıxış faylının yeganə sətrində bir tam ədəd - dağ silsiləsinin uzunluğu T metrdən çox olmayan ən cəlbedici marşrutun uzunluğunun ədədi qiyməti yerləşir.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
10 5
1 2 3 4 5 4 3 2 1 5
Çıxış verilənləri #1
18
Müəllif Daniil Neyter
Mənbə 2009 XXII All-Ukrainian Informatics Olympiad, Khmelnytskiy, March 22 - 27, Round 1