fork download
copy 
  1. #include <bits/stdc++.h>
  2. // https://c...content-available-to-author-only...y.com/contest/round-28/task/water-bottles/
  3. using namespace std;
  4. const int N = 1e5 + 3;
  5. int a[N], b[N];
  6. map<long long, vector<int>> on, off;
  7. set<long long> my;
  8. set<int> fillset;
  9. long long vol[N];
  10. int main() {
  11. 	int i, n;
  12. 	long long L, other = 0;
  13. 	scanf("%d %lld", &n ,&L);
  14. 	for(i = 1; i <= n; i++){
  15. 		scanf("%d %d", &a[i], &b[i]);
  16. 		other += a[i];
  17. 		on[a[i]].push_back(i);
  18. 		off[b[i]].push_back(i);
  19. 		my.insert(a[i]);
  20. 		my.insert(b[i]);
  21. 		vol[i] = a[i];
  22. 	}
  23. 	int cur_bottle = 0;
  24. 	for(long long w: my){
  25. 		if(cur_bottle != 0 and cur_bottle * w + other >= L){
  26. 			//finish it
  27. 			long long common = (L-other)/cur_bottle;
  28. 			long long rem = (L-other)%cur_bottle;
  29.  
  30. 			for(int pos: fillset){
  31. 				vol[pos] = common;
  32. 				if(rem>0) vol[pos]++;
  33. 				rem--;
  34. 				L -= vol[pos];
  35. 			}
  36. 			break;
  37. 		}
  38. 		for(int pos: on[w]){
  39. 			fillset.insert(pos);
  40. 			cur_bottle++;
  41. 			other -= a[pos];
  42. 		}
  43. 		for(int pos: off[w]){
  44. 			vol[pos] = w;
  45. 			L -= w;
  46. 			cur_bottle--;
  47. 			fillset.erase(pos);
  48. 		}
  49. 	}
  50. 	long long mn = 1e10, mx = 0;
  51. 	for(i = 1; i <= n; i++){
  52. 	    mn = min(mn, vol[i]);
  53. 	    mx = max(mx, vol[i]);
  54. 	}
  55. 	printf("%lld\n", mx-mn);
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 17616KB
comments (?)
stdin
copy 
3 8
0 0
3 4
2 4
stdout
copy 
4
https://ideone.com/EOmOEq
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!