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,a,...a[n] find the maximum of (ba+ba+.....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,a,...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, a, ... 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 (ba+ba+.....b[n]a[n]) subject to restrictions 1 and 2.
The sequence a is sorted in non-decreasing order i.e. a<=a<=....<=a[n]
Sample Input :2 1
Sample Output :0
Sample Input :2 0
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.
|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|
Fetching successful submissions