fork download
copy 
  1. import math
  2. def find(u, par):
  3.  
  4.     if par[u] != u:
  5.         par[u] = find(par[u], par)
  6.     return par[u]
  7.  
  8. def union(u, v, par, size):
  9.     u_root = find(u, par)
  10.     v_root = find(v, par)
  11.  
  12.     if u_root == v_root:
  13.         return 
  14.  
  15.  
  16.     if size[u_root] < size[v_root]:
  17.         par[u_root] = v_root
  18.         size[v_root] += size[u_root]
  19.     else:
  20.         par[v_root] = u_root
  21.         size[u_root] += size[v_root]
  22.  
  23. def ip():
  24.     return map(int,input().split())
  25.  
  26.  
  27.  
  28.  
  29. T=1
  30. # T=int(input())
  31. for __ in range(T):
  32.     n=int(input())
  33.     lst=[]
  34.     for _ in range(n):
  35.        a,b=ip()
  36.        lst.append([b,a])
  37.  
  38.     lst.sort()
  39.  
  40.     i=0
  41.     j=n-1
  42.  
  43.     ct=0
  44.     res=0
  45.     while i<n:
  46.         b1,a1=lst[i]
  47.         b2,a2=lst[j]
  48.         if a1==0:
  49.             i+=1
  50.             continue
  51.         if ct<lst[i][0]:
  52.             while i<=j and ct<lst[i][0]:
  53.                 diff=min(lst[i][0]-ct,lst[j][1])
  54.                 ct+=diff
  55.                 lst[j][1]-=diff
  56.                 res+=diff*2
  57.                 if lst[j][1]==0:
  58.                     j-=1
  59.         if ct>=lst[i][0]:
  60.             ct+=lst[i][1]
  61.             res+=lst[i][1]
  62.  
  63.         else:
  64.             ct+=lst[i][1]
  65.             res+=lst[i][1]*2
  66.         # print(lst,ct,res)
  67.         i+=1
  68.  
  69.     print(res)
  70.  
  71.  
  72.  
  73.  
  74.  
Success #stdin #stdout 0.11s 14064KB
comments (?)
stdin
copy 
3
3 4
1 3
1 5
stdout
copy 
8
https://ideone.com/oZXCd3
language:
Python 3 (python  3.12)
created:
2 days 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!