| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
MIN_SUM - Գումարի մինիմիզացում |
Տրված է ամբողջ թվերի n երկարության հաջորդականություն։ Հաջորդականության ցանկացած i-րդ անդամից մինչև վերջին անդամը բոլոր տարրերի ենթահաջորդականությունը կոչվում է վերջածանց։ Մեկ գործողությունով թույլատրվում է հաջորդականության որևէ վերջածանցի բոլոր տարրերի նշանները փոխել՝ դրականը դարձնել բացասական, բացասականը դրական։
Պահանջվում է առավելագույնը k հատ գործողությունների միջոցով մինիմիզացնել հաջորդականության տարրերի գումարը։
Մուտքային տվյալներ
Առաջին տողում տրված են n (1 ≤ n ≤ 500 000) և k (1 ≤ k ≤ 100) թվերը։ Հաջորդ տողում տրված են n հատ ամբողջ թվեր -109 , 109 սահմաններից։
Ելքային տվյալներ
Պահանջվում է արտածել մեկ թիվ՝ մինիմիզացված գումարը։
Օրինակ
| Մուտք | Ելք |
|---|---|
| 6 2
-1 10 6 5 -2 -3 |
-27 |
| 9 2
-1 5 -3 4 -2 6 7 -1 2 |
-19 |
Բացատրություն
Առաջին օրինակում նախ փոխենք 10-ով սկսվող վերջածանցը։ Արդյունքում վերջին երկու թվերը կդառնան դրական, երկրորդ գործողությունով դրանք կարելի է կրկին դարձնել բացասական, արդյունքում բոլոր թվերը կլինեն բացասական։
Երկրորդ օրինակում հաջորդականության երկրորդ անդամից սկվող վերջածանցի բոլոր թվերի նշանները փոխենք։ Արդյունքում գումարը կլինի -19: Կարելի է նկատել, որ սա հենց հնարավոր մինիմալ գումարն է առավելագույնը երկու գործողություն կատարելու դեպքում:
| Ավելացրեց. | Andreasyan |
| Ամսաթիվ. | 2022-02-05 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3 |
| Աղբյուրը. | Մարզային փուլ, 2021-22 |
RSS