| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
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 |
RSS