fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. const int maxN = 2e5+1;
  6. const int SIZE = 4e6;
  7. const ll INF = 0x3f3f3f3f3f3f3f3f;
  8.  
  9. struct Line {
  10.     ll m, b;
  11.     ll operator()(const ll x) const {
  12.         return m * x + b;
  13.     }
  14. } seg[SIZE];
  15.  
  16. int N, lo[SIZE], hi[SIZE];
  17. ll X, s[maxN], f[maxN];
  18.  
  19. void build(int i, int l, int r){
  20.     lo[i] = l; hi[i] = r;
  21.     seg[i] = {0, INF};
  22.     if(l == r)  return;
  23.     int m = (l+r)/2;
  24.     build(2*i, l, m);
  25.     build(2*i+1, m+1, r);
  26. }
  27.  
  28. void insert(int i, Line L){
  29.     int l = lo[i], r = hi[i];
  30.     if(l == r){
  31.         if(L(l) < seg[i](l))
  32.             seg[i] = L;
  33.         return;
  34.     }
  35.  
  36.     int m = (l+r)/2;
  37.     if(seg[i].m < L.m)  swap(seg[i], L);
  38.     if(seg[i](m) > L(m)){
  39.         swap(seg[i], L);
  40.         insert(2*i, L);
  41.     } else insert(2*i+1, L);
  42. }
  43.  
  44. ll query(int i, ll x){
  45.     int l = lo[i], r = hi[i];
  46.     if(l == r)  return seg[i](x);
  47.  
  48.     int m = (l+r)/2;
  49.     if(x < m)   return min(seg[i](x), query(2*i, x));
  50.     else        return min(seg[i](x), query(2*i+1, x));
  51. }
  52.  
  53. int main(){
  54.     scanf("%d %lld", &N, &X);
  55.     for(int i = 0; i < N; i++)  scanf("%lld", &s[i]);
  56.     for(int i = 0; i < N; i++)  scanf("%lld", &f[i]);
  57.  
  58.     build(1, 1, 1e6);
  59.     insert(1, {X, 0});
  60.     for(int i = 0; i < N-1; i++){
  61.         ll best = query(1, s[i]);
  62.         insert(1, {f[i], best});
  63.     }
  64.     printf("%lld\n", query(1, s[N-1]));
  65. }
  66.  
Success #stdin #stdout 0.02s 58772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/NrMjb9
language:
C++14 (gcc 8.3)
created:
179 days ago
visibility:
public

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!