Pleasing the Martian King

Problem code: IITI00

All submissions for this problem are available.

Freakin' news has recently claimed that they have discovered a civilization on mars and that they have established contact with the martians. Following is a summary of the dawn hour breakin' news on freakin' news :

Occassionally, the martian ministers feel the need to please their king. For this purpose, they give the king a trivial problem to solve and heap excessive praise upon him when he presents the correct solution.

This time they have given the king the following problem :
Given two positive integers n,k and n numbers a[1],a[2],...a[n] find the maximum of (b[1]a[1]+b[2]a[2]+.....b[n]a[n]) subject to the restrictions :
1) b[i] is either 1 or (-1), for all i, 1<=i<=n.
2) Exactly k b[i]'s are 1. The remaining (n-k) b[i]'s are (-1).

To make the task even easier for the king, the ministers have given the king the sequence a[1],a[2],...a[n] sorted in non-decreasing order.

The king, being lazy, has outsourced the task to freakin' news. Your job is to do this task for freakin' news.

Input Format :

The first line of input contains a single integer n. The next line consists of n space seperated integers a[1], a[2], ... a[n]. The sequence a is guaranteed to be sorted in non-decreasing order.

Output Format :

On the only line of output, output a single integer : the maximum of (b[1]a[1]+b[2]a[2]+.....b[n]a[n]) subject to restrictions 1 and 2.

Constraints :

2<=n<=100
0<=k<=n
|a[i]|<=1000
The sequence a is sorted in non-decreasing order i.e. a[1]<=a[2]<=....<=a[n]

Sample Input :

2 1
-4 -4

Sample Output :

0

Sample Input :

2 0
-2 5

Sample Output :

-3

Explanation :

1 : There are two possibilities for the sequence b : (+1,-1) and (-1,+1). Both lead to sum 0.
2 : There is only one possibility for the sequence b : (-1,-1). This leads to the sum -3.

Author: architk
Date Added: 27-03-2012
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

"The first line of input

al13n @ 31 Mar 2012 06:04 PM
"The first line of input contains a single integer n." Nope.

Please correct the input

vindu525 @ 31 Mar 2012 06:10 PM
Please correct the input format it says take n but in the example you are taking both n and k

Yes, first line contains 2

architk @ 31 Mar 2012 06:45 PM
Yes, first line contains 2 space-seperated integers : n and k. Announced.

All solutions which were not

architk @ 31 Mar 2012 08:08 PM
All solutions which were not accepted (including internal errors) are being tested again.

All solutions which were not

architk @ 31 Mar 2012 08:10 PM
All solutions which were not accepted (including internal errors) are being tested again.

And solutions which were

lopek @ 31 Mar 2012 08:16 PM
And solutions which were accepted are getting internal errors now :) ?

I had two accepted solutions

conankudo @ 31 Mar 2012 08:44 PM
I had two accepted solutions of IITI00 and IITI01, and both of them are internal errors now...?!

SUCCESSFUL SUBMISSIONS


Fetching successful submissions