The 4th(2009) ACM Programming Contest of HUST - Onsite Contest

From: 2009-12-06 12:00:00 To: 2009-12-06 17:00:00 Now: 2017-09-20 01:07:03 Status: Public

G - Reverse Number

Time Limit: 1s Memory Limit: 128MB

Submissions: 547 Solved: 116
Description
Given a non-negative integer sequence A with length N, you can exchange two adjacent numbers each time. After K exchanging operations, what’s the minimum reverse number the sequence can achieve? The reverse number of a sequence is the number of pairs (i, j) such that i < j and Ai > Aj
Input
There are multiple cases. For each case, first line contains two numbers: N, K 2<=N<=100000, 0 <= K < 2^60 Second line contains N non-negative numbers, each of which not greater than 2^30
Output
Minimum reverse number you can get after K exchanging operations.
Sample Input
3 1
3 2 1
5 2
5 1 4 3 2
Sample Output
Case #1: 2
Case #2: 5
Hint
Source
Liu Fei, HUST Campus 2009