Advertisement
Guest User

Untitled

a guest
Jul 20th, 2018
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.51 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. int main() {
  7. int n;
  8. scanf("%d", &n);
  9.  
  10. vector<pair<ll, ll>> in;
  11. for (int i = 0,a,b; i < n; i++) {
  12. scanf("%d %d", &a, &b);
  13. in.push_back({a, b});
  14. }
  15.  
  16. sort(in.begin(), in.end());
  17.  
  18. vector<pair<ll, ll>> v;
  19. for (auto p : in) {
  20. while (!v.empty() && p.second >= v.back().second)
  21. v.pop_back();
  22. v.push_back(p);
  23. }
  24.  
  25. n = v.size();
  26.  
  27. vector<ll> dp;
  28. dp.push_back(v[0].first * v[0].second);
  29.  
  30. vector<pair<int, int>> opt;
  31. opt.push_back({0, 1});
  32. int curOpt = 0;
  33.  
  34. // i >= a >= b
  35. auto isbetter = [&v, &dp](int a, int b, int i) {
  36. ll dpa = v[i].first * v[a].second + (a > 0 ? dp[a-1] : 0);
  37. ll dpb = v[i].first * v[b].second + (b > 0 ? dp[b-1] : 0);
  38.  
  39. return dpa <= dpb;
  40. };
  41.  
  42. for (int i = 1; i < n; i++) {
  43. if (curOpt+1 < opt.size() && i >= opt[curOpt+1].second)
  44. curOpt++;
  45.  
  46. int j = opt[curOpt].first;
  47.  
  48. dp.push_back(min(v[i].first * v[j].second + (j > 0 ? dp[j-1] : 0),
  49. v[i].first * v[i].second + dp[i-1]));
  50.  
  51. while (!opt.empty() && opt.back().second >= i && isbetter(i, opt.back().first, opt.back().second))
  52. opt.pop_back();
  53.  
  54. if (!opt.empty()) {
  55. int l = opt.back().second, r = n-1;
  56. if (!isbetter(i, opt.back().first, r))
  57. continue;
  58. while (l < r) {
  59. int m = (l + r) >> 1;
  60. if (isbetter(i, opt.back().first, m)) r = m;
  61. else l = m+1;
  62. }
  63. opt.push_back({i, l});
  64. } else {
  65. opt.push_back({i, i+1});
  66. }
  67. }
  68.  
  69. printf("%lld\n", dp.back());
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement