fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ldb long double
  4. #define fi first
  5. #define se second
  6. #define sza(a) (int)a.size()
  7. #define pir pair<int,int>
  8. #define pirll pair<ll,ll>
  9. using namespace std;
  10. const int maxn = 5e5 + 5;
  11.  
  12. pir a[maxn];
  13. multiset <int> s;
  14.  
  15. ll solve(int n){
  16. 	sort(a + 1,a + 1 + n);
  17. 	ll res = 0,cur = a[1].fi;
  18.  
  19. 	int p = 1;
  20. 	while (p <= n){
  21. 		int nxt = p;
  22. 		cur = max(cur,(ll)a[p].fi);
  23. 		while (nxt <= n && a[nxt].fi == a[p].fi) nxt++;
  24.  
  25. 		for (int i = p ; i < nxt ; i++)
  26. 		  s.insert(a[i].se);
  27.  
  28. 		if (nxt > n) break;
  29. 		int money = a[nxt].fi - a[p].fi;
  30.  
  31. 		while (money > 0 && s.size()){
  32. 			int t = *s.begin();
  33. 			s.erase(s.begin());
  34.  
  35. 			int M = min(t,money);
  36. 			t -= M;
  37. 			money -= M;
  38. 			cur += M;
  39.  
  40. 			if (t > 0) s.insert(t);
  41. 			else res += cur;
  42. 		}
  43. 		p = nxt;
  44. 	}
  45.  
  46. 	for (auto it = s.begin() ; it != s.end() ; it++){
  47. 		cur += *it;
  48. 		res += cur;
  49. 	}
  50.  
  51. 	return res;
  52. }
  53.  
  54. int main(){
  55. 	ios_base::sync_with_stdio(false);
  56. 	cin.tie(0);cout.tie(0);
  57.  
  58. 	int n;
  59. 	cin >> n;
  60. 	for (int i = 1 ; i <= n ; i++) cin >> a[i].fi >> a[i].se;
  61. 	cout << solve(n);
  62.  
  63. 	return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fYkYSR
language:
C++14 (gcc 8.3)
created:
6 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!