Գումարի մինիմիզացում

Տրված է ամբողջ թվերի n երկարության հաջորդականություն։ Հաջորդականության ցանկացած i-րդ անդամից մինչև վերջին անդամը բոլոր տարրերի ենթահաջորդականությունը կոչվում է վերջածանց։ Մեկ գործողությունով թույլատրվում է հաջորդականության որևէ վերջածանցի բոլոր տարրերի նշանները փոխել՝ դրականը դարձնել բացասական, բացասականը դրական։

Պահանջվում է առավելագույնը k հատ գործողությունների միջոցով մինիմիզացնել հաջորդականության տարրերի գումարը։

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

Առաջին տողում տրված են n (1 ≤ n ≤ 500 000) և k (1 ≤ k ≤ 100) թվերը։ Հաջորդ տողում տրված են n հատ ամբողջ թվեր  սահմաններից։

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

Պետք է արտածել մեկ թիվ՝ ընտրված աշակերտների համապատասխան առարկաներից հավաքած միավորների մաքսիմալ հնարավոր գումարը:

Օրինակ

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

Առաջին օրինակում նախ փոխենք 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