We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
import java.util.*;
This is the solution came up with, the formatting might be a little easier to understand.
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int numContests = in.nextInt();
int maxLosses = in.nextInt();
ArrayList<Integer>contestLucks = new ArrayList<Integer>();
int totalLuck = 0;
for(int i = 0;i<numContests;i++){
int currContestLuck = in.nextInt();
int temp = in.nextInt();
if(temp ==0)totalLuck+=currContestLuck;
else contestLucks.add(currContestLuck);
}
Collections.sort(contestLucks);
for(int i = 0;i<contestLucks.size();i++){
if(i<contestLucks.size()-maxLosses)totalLuck-=contestLucks.get(i);
else totalLuck +=contestLucks.get(i);
}
System.out.println(totalLuck);
}
}
Unfortunately, the "Collections.sort" method degrades the performance to O(N*log(N)). Besides, the "ArrayList" collection uses an additional O(N) amount of memory. An optiomal solution should run in O(N*log(K)) time and use O(K) space.
Luck Balance
You are viewing a single comment's thread. Return to all comments →
import java.util.*; This is the solution came up with, the formatting might be a little easier to understand.
Unfortunately, the "Collections.sort" method degrades the performance to O(N*log(N)). Besides, the "ArrayList" collection uses an additional O(N) amount of memory. An optiomal solution should run in O(N*log(K)) time and use O(K) space.