/**
* Sample solution for Balloons
* In SE Regional, 78 submissions, 15 correct (17%)
*/
#include
#include
#include
using namespace std;
//each team has a number of balloons it needs, and a distance from each room
struct Team {
int nBalloons;
int da;
int db;
};
// compare two teams
bool operator< (const Team& left, const Team& right)
{
//determine difference between rooms A and B ("penalty" if go to non-preferred room)
int ld = abs(left.da - left.db);
int rd = abs(right.da - right.db);
//if the first team has a greater penalty than the second, return true; we want the sort to put max penalty first
//so it is "less" when doing an ascending sort
return ld > rd;
}
/**
* Process a single dataset for the problem.
* Return true if successful. Return false if we encounter the
* end of input marker or an unreocverable I/O error,
*/
bool processDataSet ()
{
// read the data in
int N, A, B;
// total number of teams
cin >> N;
// quit if get total number of teams = 0
if (N == 0)
return false;
// read in number of balloons in A and B
cin >> A >> B;
// create an array of Teams
Team* teams = new Team[N];
// read in the data for each team
for (int i = 0; i < N; ++i)
cin >> teams[i].nBalloons >> teams[i].da >> teams[i].db;
// Solve
// use a built-in (STL) sorting algorithm to ascending-sort the teams
sort (teams, teams+N);
// total distance traveled = 0
int total = 0;
// for each team, in sorted order
for (int i = 0; i < N; ++i)
{
int balloonsFromA;
int balloonsFromB;
// if teams distance from Room A is less than distance from Room B
if (teams[i].da < teams[i].db)
{
// balloons can get from A is either teams request (if A holds more), or total in A (may be less than request)
balloonsFromA = min(teams[i].nBalloons, A);
// take everything else from B
balloonsFromB = teams[i].nBalloons - balloonsFromA;
}
else
{
// same logic as above, just switched since Room B is closer
balloonsFromB = min(teams[i].nBalloons, B);
balloonsFromA = teams[i].nBalloons - balloonsFromB;
}
// for this team, distance covered from A is distance from A * number of balloons from A
int distA = balloonsFromA * teams[i].da;
// same logic for from B
int distB = balloonsFromB * teams[i].db;
// update balloon counts in rooms
A -= balloonsFromA;
B -= balloonsFromB;
// update total distance traveled
total += distA + distB;
}
cout << total << endl;
return true;
}
int main (int argc, char** argv)
{
bool finished = false;
while (!finished)
{
finished = !processDataSet();
}
}