The Java Program: YiuBalloon.java
1
2
3
4
5
6
7
8 import java.io.*;
9 import java.util.*;
10
11 public class YiuBalloon
12 {
13 public Scanner in = new Scanner(System.in);
14 public PrintStream out = System.out;
15
16 public int n, A, B;
17 public int Ar, Br;
18
19 public ArrayList<Team> Av, Bv;
20
21 public void main() throws Exception
22 {
23 in = new Scanner( new File( "balloons.judge" ) );
24 out = new PrintStream( new FileOutputStream( "balloonsyiu.out" ) );
25 n = in.nextInt();
26 while(n > 0)
27 {
28 A = in.nextInt();
29 B = in.nextInt();
30
31 Ar = Br = 0;
32 Av = new ArrayList<Team>();
33 Bv = new ArrayList<Team>();
34
35 int K, DA, DB;
36 int res = 0;
37
38 for(int i = 0; i < n; ++i)
39 {
40 K = in.nextInt();
41 DA = in.nextInt();
42 DB = in.nextInt();
43
44 if(DA < DB)
45 {
46 Ar += K;
47 res += DA * K;
48 Av.add(new Team(K, DB - DA));
49 }
50 else
51 {
52
53 Br += K;
54 res += DB * K;
55 Bv.add(new Team(K, DA - DB));
56 }
57 }
58
59 Collections.sort(Av);
60 Collections.sort(Bv);
61
62 if(Ar > A) res += move(Ar - A, Av);
63 if(Br > B) res += move(Br - B, Bv);
64
65 out.println(res);
66
67 n = in.nextInt();
68 }
69 }
70
71 public int move(int mv, ArrayList<Team> v)
72 {
73 int res = 0;
74 for(int i = 0; i < v.size() && mv > 0; ++i)
75 {
76 Team T = v.get(i);
77 if(T.count < mv)
78 {
79 res += T.count * T.cost;
80 mv -= T.count;
81 }
82 else
83 {
84
85 res += mv * T.cost;
86 mv -= mv;
87 }
88 }
89
90 return res;
91 }
92
93 private class Team implements Comparable<Team>
94 {
95 public int cost, count;
96
97 public Team(int countIn, int costIn)
98 {
99 cost = costIn;
100 count = countIn;
101 }
102
103
104 public int compareTo(Team T)
105 {
106 if(cost != T.cost) return cost - T.cost;
107 return count - T.count;
108 }
109 }
110
111 public static void main(String[] args) throws Exception
112 {
113 (new YiuBalloon()).main();
114 }
115 }