fork download
copy 
  1. from __future__ import division
  2.  
  3. from heapq import *
  4. t = int(raw_input())
  5. class Job:
  6.     def __init__(self, cost, time , deadline):
  7.         self.cost = cost
  8.         self.time = time
  9.         self.deadline = deadline
  10.  
  11.     def __lt__(self, other):
  12.         if other.deadline != self.deadline:
  13.             return self.deadline < other.deadline
  14.         else:
  15.             self.cost > other.cost
  16.  
  17.  
  18. for _ in range(t):
  19.     heaplist = []
  20.     total_cost = 0
  21.     n = int(raw_input())
  22.     dic_tuple = {}
  23.     dic_time_required = {}
  24.     ds = set()
  25.     deadlines = []
  26.     for __ in range(n):
  27.         a, time, deadline = map(int, raw_input().split())
  28.         job = Job(a, time, deadline)
  29.         deadlines.append(job)
  30.  
  31.     deadlines = sorted(deadlines)
  32.     time = 0
  33.     ans = 0
  34.     for deadline in deadlines:
  35.         time += deadline.time
  36.         heappush(heaplist, (-deadline.cost, -float(deadline.time / deadline.cost)))
  37.         while time > deadline.deadline:
  38.             temp_cost, temp_ratio = heappop(heaplist)
  39.             cost, ratio = -temp_cost, -temp_ratio
  40.             if time - cost * ratio > deadline.deadline:
  41.                 time -= cost * ratio
  42.                 ans += ratio
  43.  
  44.             else:
  45.                 x = (time - deadline.deadline) / cost
  46.                 time -= cost * x
  47.                 ans += x
  48.                 heappush(heaplist, (-cost, -(ratio - x)))
  49.     print("%.2f" % ans)
  50.  
  51.  
Runtime error #stdin #stdout #stderr 0.04s 64740KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "prog.py", line 4, in <module>
    t = int(raw_input())
EOFError
https://ideone.com/dYEbOp
language:
Python (PyPy 2.7.13)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!