Advertisement
Guest User

Untitled

a guest
Jun 25th, 2016
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.96 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.HashMap;
  4. import java.util.NavigableSet;
  5. import java.util.Scanner;
  6. import java.util.SortedSet;
  7. import java.util.Stack;
  8. import java.util.TreeMap;
  9. import java.util.TreeSet;
  10.  
  11. /*
  12. * To change this license header, choose License Headers in Project Properties.
  13. * To change this template file, choose Tools | Templates
  14. * and open the template in the editor.
  15. */
  16. /**
  17. *
  18. * @author Vendetta
  19. */
  20. public class Main {
  21.  
  22. static TreeMap<Integer, ArrayList<Integer>> map;
  23.  
  24. public static void main(String args[]) {
  25. Scanner sc = new Scanner(System.in);
  26. int N, H, v, t, total, T, V;
  27. ArrayList<Integer> list;
  28. TreeSet<Integer> timeLine = new TreeSet();
  29. while (sc.hasNext()) {
  30. map = new TreeMap<>();
  31. N = sc.nextInt();
  32. H = sc.nextInt();
  33. for(int i=1;i<=H;i++){
  34. timeLine.add(i);
  35. }
  36. total = 0;
  37. for (int i = 0; i < N; i++) {
  38. v = sc.nextInt();
  39. total += v;
  40. t = sc.nextInt();
  41. list = map.get(v);
  42. if (list == null) {
  43. list = new ArrayList<>();
  44. }
  45. list.add(t);
  46. map.put(v, list);
  47. }
  48. T = 0;
  49. V = 0;
  50. Integer temp,lower;
  51. for (Integer cost : map.descendingKeySet()) {
  52. list = map.get(cost);
  53. Collections.sort(list);
  54. for(int i=0;i<list.size() && T< H;i++){
  55. temp= list.get(i);
  56. lower = timeLine.floor(temp);
  57. if(lower!=null){
  58. V+=cost;
  59. T++;
  60. timeLine.remove(lower);
  61. }
  62. }
  63. }
  64. System.out.println((total - V));
  65. }
  66. }
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement