Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

TOURISM21 - Տուրիզմ 1

Ինչպես հիշում եք, Հայկը դեռ մարզային փուլին գնում էր դպրոց, իսկ հիմա արդեն միայնակ պետք է գնա ճանապարհորդության։ Հայկը պլանավորում է այցելել իրարից տարբեր n տեսարժան վայրեր։
Տեսարժան վայրերը համարակալված են 1ից n թվերով, և Հայկը պետք է այցելի դրանք ճիշտ նույն հերթականությամբ։ Մեկ օրում Հայկը կարող է այցելել ամենաշատը k տեսարժան վայրեր և ցանկանում է պլանավորել իր ճանապարհորդությունն այնպես, որ ծախսած օրերի քանակը լինի հնարավորինս քիչ։
Տեսարժան վայրերից յուրաքանչյուրը ունի գեղեցկության չափանիշ, որոնք ձեզ տրված են։ Հայկը ամեն օր ստանում է իր այցելած տեսարժան վայրերի գեղեցկության չափանիշներից առավելագույնին համարժեք հաճույք։ Ձեր խնդիրն է պլանավորել Հայկի ճանապարհորդությունն այնպես, որ նա այդ ճանապարհորդությունից ստանա հնարավորինս շատ հաճույք, այսինքն բոլոր օրերում ստացած հաճույքների գումարը լինի հնարավորինս մեծ։

Մուտքային տվյալներ

Առաջին տողում տրված է երկու բնական թիվ՝ n և k (1 ≤ k ≤ n ≤ 300). տեսարժան վայրերի քանակը և օրվա ընթացքում առավելագույն տեսարժան վայրերը, որոնք Հայկը կարող է այցելել։
Հաջորդ n տողերից յուրաքանչյուրում տրված է մեկ բնական թիվ՝ a[i] (1 ≤ a[i] ≤ 109)․ iրդ վայրի գեղեցկության չափանիշը:

Ելքային տվյալներ

Պետք է արտածել մեկ թիվ՝ առավելագույն հաճույքը, որը Հայկը կարող է ստանալ։

Օրինակ

Մուտք Ելք

5 3

2 5 7 1 4

12
Բացատրություն

Հայկը ցանկանում է այցելել բոլոր տեսարժան վայրերը հնարավորինս քիչ օրերում, և նա այս օրինակում կարող է դա անել 2 օրում․

  • Առաջին օր. Հայկը կայցելի առաջին երկու տեսարժան վայրերը՝ ստանալով max(a[1], a[2]) = 5 հաճույք,
  • Երկրորդ օր. Հայկը կայցելի մնացած երեք տեսարժան վայրերը՝ ստանալով max(a[3], a[4], a[5]) = 7 հաճույք:

 


Ավելացրեց.Andreasyan
Ամսաթիվ.2021-03-22
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3
Աղբյուրը.Հանրապետական փուլ, 2020-2021

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.