Advertisement
MaxObznyi

Untitled

Feb 9th, 2021
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.93 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. const int N = 1e6 + 6;
  6.  
  7. int n;
  8. int a[N], b[N];
  9. int ans[N];
  10. int x, y;
  11.  
  12. stack<int> t;
  13. int sum = 0;
  14.  
  15. signed main() {
  16. ios_base::sync_with_stdio(0);
  17. cin.tie(0);
  18. cout.tie(0);
  19. int res = -1e18;
  20. cin >> n;
  21. for (int i = 1; i <= n; i++)
  22. cin >> a[i] >> b[i];
  23. cin >> x >> y;
  24. for (int i = 1; i <= n; i++) {
  25. ans[i] += sum * y;
  26. while (t.size() > 0 && a[t.top()] <= a[i])
  27. sum -= b[t.top()], t.pop();
  28. t.push(i);
  29. sum += b[i];
  30. }
  31. t = {};
  32. sum = 0;
  33. for (int i = n; i > 0; i--) {
  34. ans[i] += sum * y;
  35. while (t.size() > 0 && a[t.top()] <= a[i])
  36. sum -= b[t.top()], t.pop();
  37. t.push(i);
  38. sum += b[i];
  39. }
  40. for (int i = 1; i <= n; i++)
  41. res = max(res, ans[i] + b[i] * y - a[i] * x);
  42. cout << res;
  43. return 0;
  44. }
  45.  
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement