fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #define pb push_back
  5. #define mp make_pair
  6. #define fs first
  7. #define sc second
  8. #define sz(a) ((int) (a).size())
  9. #define int64 long long
  10. using namespace std;
  11.  
  12. const int N = 250 * 1000 + 7;
  13. const int B = 300;
  14.  
  15. int a[N], b[N], bucket[N], n;
  16. vector< pair<int, int> > alla, allb;
  17.  
  18. struct t_bucket {
  19. 	int pos;
  20. 	vector<int> elems;
  21. 	vector< pair<int, int64> > data, lines;
  22. 	vector<int64> pts;
  23.  
  24. 	void add_elem(int elem) {
  25. 		vector<int>::iterator pos = lower_bound(elems.begin(), elems.end(), elem);
  26. 		elems.insert(pos, elem);
  27. 	}
  28.  
  29. 	int64 ceiling(int64 a, int64 b) {
  30. 		return (a + b - 1) / b;
  31. 	}
  32.  
  33. 	void add(int value) {
  34. 		add_elem(value);
  35. 		lines.clear();
  36. 		data.clear();
  37. 		pts.clear();
  38. 		for (int i = 0; i < sz(elems); ++i) {
  39. 			if ((i == 0) || (elems[i] != elems[i - 1])) {
  40. 				lines.pb(mp(elems[i], elems[i] * (int64) (sz(elems) - i)));
  41. 			}
  42. 		}
  43. 		pts.pb(0);
  44. 		data.pb(lines[0]);
  45. 		for (int i = 1; i < sz(lines); ++i) {
  46. 			while (!data.empty() && (lines[i].fs * (int64) pts.back() + lines[i].sc >= data.back().fs * (int64) pts.back() + data.back().sc)) {
  47. 				data.pop_back();
  48. 				pts.pop_back();
  49. 			}
  50. 			pts.pb(data.empty() ? 0 : max(0LL, ceiling(data.back().sc - lines[i].sc, lines[i].fs - data.back().fs)));
  51. 			data.pb(lines[i]);
  52. 		}
  53. 		pos = 0;
  54. 	}
  55.  
  56. 	int64 get_value(int pos, int size) {
  57. 		return data[pos].fs * (int64) size + data[pos].sc;
  58. 	}
  59.  
  60. 	int64 get_best(int size) {
  61. 		if (data.empty()) {
  62. 			return 0;
  63. 		}
  64. 		while ((pos + 1 < sz(data)) && (get_value(pos + 1, size) >= get_value(pos, size))) {
  65. 			pos++;
  66. 		}
  67. 		return get_value(pos, size);
  68. 	}
  69. } buckets[N / B + 1];
  70.  
  71. int64 get_answer() {
  72. 	int size = 0;
  73. 	int64 best = 0;
  74. 	for (int i = 0; i <= (n - 1) / B; ++i) {
  75. 		best = max(best, buckets[i].get_best(size));
  76. 		size += sz(buckets[i].elems);
  77. 	}
  78. 	return best;
  79. }
  80.  
  81. int main() {
  82. 	scanf("%d", &n);
  83. 	for (int i = 0; i < n; ++i) {
  84. 		scanf("%d%d", &b[i], &a[i]);
  85. 		alla.pb(mp(a[i], i));
  86. 		allb.pb(mp(b[i], i));
  87. 	}
  88. 	sort(alla.rbegin(), alla.rend());
  89. 	for (int i = 0; i < n; ++i) {
  90. 		bucket[alla[i].sc] = i / B;
  91. 	}
  92. 	sort(allb.begin(), allb.end());
  93. 	int64 best = 0;
  94. 	for (int i = 0; i < n; ++i) {
  95. 		int num = allb[i].sc;
  96. 		best = max(best, get_answer() + (n - i) * (int64) b[num]);
  97. 		buckets[bucket[num]].add(a[num]);
  98. 	}
  99. 	printf("%lld\n", best);
  100. 	return 0;
  101. }
Success #stdin #stdout 0s 18256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/12D1zF
language:
C++14 (gcc 8.3)
created:
5 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!