codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

262B.md (1731B)


      1 Source: https://codeforces.com/problemset/problem/262/B
      2 
      3 B. Roma and Changing Signs
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Roma works in a company that sells TVs. Now he has to prepare a report for the last year.
     22 
     23 Roma has got a list of the company's incomes. The list is a sequence that consists of *n* integers. The total income of the company is the sum of all integers in sequence. Roma decided to perform exactly *k* changes of signs of several numbers in the sequence. He can also change the sign of a number one, two or more times.
     24 
     25 The operation of changing a number's sign is the operation of multiplying this number by -1.
     26 
     27 Help Roma perform the changes so as to make the total income of the company (the sum of numbers in the resulting sequence) maximum. Note that Roma should perform exactly *k* changes.
     28 
     29 Input
     30 
     31 The first line contains two integers *n* and *k* (1 ≤ *n*, *k* ≤ 105), showing, how many numbers are in the sequence and how many swaps are to be made.
     32 
     33 The second line contains a non-decreasing sequence, consisting of *n* integers *a**i* (|*a**i*| ≤ 104).
     34 
     35 The numbers in the lines are separated by single spaces. Please note that the given sequence is sorted in non-decreasing order.
     36 
     37 Output
     38 
     39 In the single line print the answer to the problem — the maximum total income that we can obtain after exactly *k* changes.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3 2  
     47 -1 -1 1
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 3
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 3 1  
     60 -1 -1 1
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 1
     67 ```
     68 
     69 Note
     70 
     71 In the first sample we can get sequence [1, 1, 1], thus the total income equals 3.
     72 
     73 In the second test, the optimal strategy is to get sequence [-1, 1, 1], thus the total income equals 1.