nik7's blog

By nik7, history, 5 weeks ago, In English,

I am talking about this problem from last contest. My approach is: First I sorted the array of pairs according to sweetness value. Then I iterated from the back and inserted k — 1 lengths in a priority queue and computed the answer considering every element as the minimum sweetness value. Then I started another loop for the remaining elements in the array. So at each point my priority queue is having k — 1 largest lengths excluding the current length. And I am updating the values in the queue correctly. What I am doing wrong here

 
 
 
 

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Test:

7 5
39058 576000
175945 129701
114638 209576
811260 401606
935588 332159
757168 895242
336278 481782
943014 454698

Right answer is 1256659801972

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Okay just tell me which songs have to be selected to get the answer you mentioned.