#include #include #include using namespace std; struct contract { unsigned a, b, d; // coefficient of a contract unsigned t; // job time worked contract(unsigned a, unsigned b, unsigned d) : a(a), b(b), d(d) { } contract(const contract& c, unsigned t) : a(c.a), b(c.b), d(c.d), t(t) { } }; struct order_d { bool operator () (const contract& c1, const contract& c2) { // d ASC, a ASC - reversed because priority_queue if(c1.d != c2.d) return c1.d > c2.d; return c1.a > c2.a; } }; struct order_a { bool operator () (const contract& c1, const contract& c2) { // a DESC, t ASC - reversed because priority_queue if(c1.a != c2.a) return c1.a < c2.a; return c1.t > c2.t; } }; int main() { // input contracts int N; cin >> N; priority_queue, order_d > cs; while(N-- > 0) { unsigned a, b, d; cin >> a >> b >> d; cs.push(contract(a, b, d)); } // scheduling phase priority_queue, order_a > finished; // ^ contains only time-reducible contracts (t > 0) to reduce computation double payment = 0.0; unsigned start_time = 0; while(! cs.empty()) { const contract c = cs.top(); cs.pop(); if(start_time + c.b > c.d) { finished.push(contract(c, c.b)); // greedy optimization loop unsigned dt = start_time + c.b - c.d; //cerr << "reducing time = " << dt << endl; while(dt > 0 && ! finished.empty()) { contract r = finished.top(); finished.pop(); unsigned tm = min(r.t, dt); //cerr << " ct a=" << r.a << " t=" << r.t << " / tm=" << tm << endl; payment += (double)tm / r.a; if(r.t - tm > 0) finished.push(contract(r, r.t - tm)); dt -= tm; } assert(dt == 0); // impossible case start_time = c.d; } else { // no need to reduce time finished.push(contract(c, c.b)); start_time += c.b; } } // result static char buffer[16384]; snprintf(buffer, sizeof buffer, "%.2lf", payment); cout << buffer << endl; return 0; }