MinhNGUYEN2k4

dcva

Sep 21st, 2021
484
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 100005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. typedef int ftype;
  25. typedef complex<ftype> point;
  26. const int inf = 1e10;
  27. const int minf = -1e10;
  28. #define x real
  29. #define y imag
  30.  
  31. vector<point> hull, vecs;
  32.  
  33. ftype cross(point a, point b){
  34.     return (conj(a)*b).imag();
  35. }
  36.  
  37. ftype dot(point a, point b){
  38.     return (conj(a)*b).real();
  39. }
  40.  
  41. void add_line(ftype k, ftype b){
  42.     point nw = {k,b};
  43.     //dot > 0 -> k giam dan
  44.     //dot < 0 -> k tang dan
  45.     while (vecs.size() && dot(vecs.back(),(nw-hull.back()))>0){
  46.         vecs.pop_back();
  47.         hull.pop_back();
  48.     }
  49.     if (hull.size()){
  50.         vecs.push_back(point(1i)*(nw-hull.back()));
  51.     }
  52.     hull.push_back(nw);
  53. }
  54.  
  55. ftype get(ftype x){
  56.     point q = {x,1};
  57.     auto it = lower_bound(vecs.begin(),vecs.end(),q,
  58.     [](point a, point b){
  59.             return cross(a,b)>0;
  60.     });
  61.     //min cross > 0
  62.     //max cross < 0
  63.     return dot(q,hull[it-vecs.begin()]);
  64. }
  65.  
  66. int n,c;
  67. int dp[N], a[N], b[N];
  68.  
  69. void readfile()
  70. {
  71.     ios_base::sync_with_stdio(false);
  72.     cin.tie(0);cout.tie(0);
  73.     if (fopen(Task".inp","r"))
  74.     {
  75.         freopen(Task".inp","r",stdin);
  76.         //freopen(Task".out","w",stdout);
  77.     }
  78.     cin >> n >> c;
  79.     for(int i=1; i<=n; i++) cin >> a[i];
  80.     for(int i=1; i<=n; i++) cin >> b[i];
  81. }
  82.  
  83. void proc()
  84. {
  85.     dp[1] = c;
  86.     add_line(b[1],dp[1]);
  87.     int Min = dp[1];
  88.     for(int i=2; i<=n; i++){
  89.         dp[i] = get(a[i]);
  90.         if (b[i]<b[i-1] || (b[i]==b[i-1] && dp[i]<Min)) add_line(b[i],dp[i]);
  91.     }
  92.     cout << dp[n];
  93. }
  94.  
  95. signed main()
  96. {
  97.     readfile();
  98.     proc();
  99.     return 0;
  100. }
  101.  
RAW Paste Data