fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair <long long, long long> ii;
  5.  
  6. const int N = 1e5 + 10;
  7.  
  8. int n, m, k;
  9. ii A[N], p[N];
  10. long long t[N];
  11.  
  12. ii operator - (ii a, ii b) { return make_pair(b.first - a.first, b.second - a.second); }
  13. long long operator * (ii a, ii b) { return a.first * b.second - a.second * b.first; }
  14.  
  15. bool cw(ii a, ii b, ii c) { return (b - a) * (c - b) < 0; }
  16.  
  17. void load() {
  18. scanf("%d%d", &n, &m);
  19. for (int i = 1; i <= n; ++i) {
  20. scanf("%d", &t[i]);
  21. t[i] += t[i - 1];
  22. }
  23. for (int i = 1; i <= n; ++i)
  24. A[i] = make_pair(t[i - 1], t[i]);
  25. }
  26.  
  27. void findConvexLine() {
  28. k = 0;
  29. p[k++] = make_pair(0, 0);
  30. for (int i = 1; i <= n; ++i) {
  31. while (k > 1 && !cw(p[k - 2], p[k - 1], A[i])) k--;
  32. p[k++] = A[i];
  33. }
  34. }
  35.  
  36. long long get(int x, int y) {
  37. //ii v = make_pair(x, y);
  38. int l = 0, r = k - 2, cur = 0;
  39. while (l <= r) { // (l - 1) * v <= 0 && (r + 1) * v > 0
  40. int mid = (l + r) >> 1;
  41. if ((p[mid + 1].first - p[mid].first) * y <= (p[mid + 1].second - p[mid].second) * x) {
  42. l = mid + 1;
  43. cur = l;
  44. } else {
  45. r = mid - 1;
  46. }
  47. }
  48. return make_pair(x, y) * p[cur];
  49. }
  50.  
  51. void process() {
  52. findConvexLine();
  53. int x = 0, y = 0;
  54. long long delay = 0;
  55. for (int i = 1; i <= m; ++i) {
  56. scanf("%d", &y);
  57. delay += get(x, y);
  58. // cerr << get(x, y) << "\n";
  59. x = y;
  60. }
  61. long long ans = delay + 1ll * t[n] * x;
  62. printf("%lld\n", ans);
  63. }
  64.  
  65. int main() {
  66.  
  67. load();
  68. process();
  69.  
  70. return 0;
  71. }
  72.  
Success #stdin #stdout 0s 19144KB
stdin
Standard input is empty
stdout
0