Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.HashMap;
- import java.util.NavigableSet;
- import java.util.Scanner;
- import java.util.SortedSet;
- import java.util.Stack;
- import java.util.TreeMap;
- import java.util.TreeSet;
- /*
- * To change this license header, choose License Headers in Project Properties.
- * To change this template file, choose Tools | Templates
- * and open the template in the editor.
- */
- /**
- *
- * @author Vendetta
- */
- public class Main {
- static TreeMap<Integer, ArrayList<Integer>> map;
- public static void main(String args[]) {
- Scanner sc = new Scanner(System.in);
- int N, H, v, t, total, T, V;
- ArrayList<Integer> list;
- TreeSet<Integer> timeLine = new TreeSet();
- while (sc.hasNext()) {
- map = new TreeMap<>();
- N = sc.nextInt();
- H = sc.nextInt();
- for(int i=1;i<=H;i++){
- timeLine.add(i);
- }
- total = 0;
- for (int i = 0; i < N; i++) {
- v = sc.nextInt();
- total += v;
- t = sc.nextInt();
- list = map.get(v);
- if (list == null) {
- list = new ArrayList<>();
- }
- list.add(t);
- map.put(v, list);
- }
- T = 0;
- V = 0;
- Integer temp,lower;
- for (Integer cost : map.descendingKeySet()) {
- list = map.get(cost);
- Collections.sort(list);
- for(int i=0;i<list.size() && T< H;i++){
- temp= list.get(i);
- lower = timeLine.floor(temp);
- if(lower!=null){
- V+=cost;
- T++;
- timeLine.remove(lower);
- }
- }
- }
- System.out.println((total - V));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement