Գումարի մինիմիզացում
Տրված է ամբողջ թվերի
n երկարության հաջորդականություն։ Հաջորդականության ցանկացած i-րդ անդամից մինչև վերջին անդամը բոլոր տարրերի ենթահաջորդականությունը կոչվում է վերջածանց։ Մեկ գործողությունով թույլատրվում է հաջորդականության որևէ վերջածանցի բոլոր տարրերի նշանները փոխել՝ դրականը դարձնել բացասական, բացասականը դրական։Պահանջվում է առավելագույնը
k հատ գործողությունների միջոցով մինիմիզացնել հաջորդականության տարրերի գումարը։Մուտքային տվյալներ
Առաջին տողում տրված են
n (1 ≤ n ≤ 500 000) և k (1 ≤ k ≤ 100) թվերը։ Հաջորդ տողում տրված են n հատ ամբողջ թվեր Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ ընտրված աշակերտների համապատասխան առարկաներից հավաքած միավորների մաքսիմալ հնարավոր գումարը:
Օրինակ
Մուտք | Ելք |
6 2
-1 10 6 5 -2 -3 | -27 |
9 2
-1 5 -3 4 -2 6 7 -1 2 | -19 |
Բացատրություն
Առաջին օրինակում նախ փոխենք 10-ով սկսվող վերջածանցը։ Արդյունքում վերջին երկու թվերը կդառնան դրական, երկրորդ գործողությունով դրանք կարելի է կրկին դարձնել բացասական, արդյունքում բոլոր թվերը կլինեն բացասական։
Երկրորդ օրինակում հաջորդականության երկրորդ անդամից սկվող վերջածանցի բոլոր թվերի նշանները փոխենք։ Արդյունքում գումարը կլինի -19: Կարելի է նկատել, որ սա հենց հնարավոր մինիմալ գումարն է առավելագույնը երկու գործողություն կատարելու դեպքում:
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները,
- Ենթախնդիր 1 (16 միավոր)
n, k ≤ 20
- Ենթախնդիր 2 (9 միավոր)
n ≤ 100000, k = 1
- Ենթախնդիր 3 (13 միավոր)
n ≤ 100000, k = 2:
- Ենթախնդիր 4 (19 միավոր)
n ≤ 1000, k ≤ 50:
- Ենթախնդիր 5 (21 միավոր)
n ≤ 100000, k ≤ 100:
- Ենթախնդիր 6 (22 միավոր)
n ≤ 500000, k ≤ 100:
Աղբյուրը՝ Մարզային 2022
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB