fork(2) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Iv2qUc
language:
C++ (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!