Advertisement
Gigo_G

Untitled

Feb 24th, 2024
446
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef signed long long ll;
  4.  
  5. const ll MAXN = 2*1e5 + 7;
  6. const ll MAXC = 1e12 + 7;
  7. const ll MAXH = 1e6 + 7;
  8.  
  9. ll n, c;
  10. vector<ll> h;
  11.  
  12. ll dp[MAXN];
  13.  
  14. deque<pair<ll, ll>> q;
  15.  
  16. double i(const pair<ll, ll>& a, const pair<ll, ll> b){ /// interesect
  17.     return ((double)(b.second - a.second))/(a.first - b.first);
  18. }
  19. double e(const pair<ll, ll>& line, double x){ /// evaluate
  20.     return line.first * x  + line.second;
  21. }
  22.  
  23. void add(pair<ll, ll> nw){
  24.     if(q.size() < 2){ q.push_back(nw); return; }
  25.     pair<ll, ll> a = q.back();
  26.     pair<ll, ll> b = *prev(q.end(), 2);
  27.     while(q.size() >= 2 && (i(a, b) > i(b, nw))){
  28.         q.pop_back();
  29.         a = b;
  30.         b = *prev(q.end(), -2);
  31.     }
  32.     q.push_back(nw);
  33. }
  34. ll query(double x){
  35.     if(q.size() < 2){ return e(q.front(), x); }
  36.     pair<ll, ll> a = q.front();
  37.     pair<ll, ll> b = *next(q.begin());
  38.     while(q.size() >= 2 && i(a, b) < x){
  39.         q.pop_front();
  40.         a = b;
  41.         b = *next(q.begin());
  42.     }
  43.     return e(q.front(), x);
  44. }
  45.  
  46. int main(){
  47.     cin >> n >> c;
  48.     h.resize(n);
  49.     for(ll i = 0; i < n; i++){
  50.         cin >> h[i];
  51.     }
  52.  
  53.     for(ll i = 0; i < n; i++){
  54. ///        h[i]*h[i] - 2*h[i]*h[j] + h[j]*h[j] + dp[j] + c;
  55.         if(i == 0){ dp[i] = 0; }
  56.         else{
  57.             dp[i] = query(h[i]) + h[i]*h[i] + c;
  58.         }
  59.  
  60.         pair<ll, ll> newLine = {-2*h[i], h[i]*h[i] + dp[i]};
  61.         add(newLine);
  62.     }
  63.  
  64.     cout << dp[n-1] << '\n';
  65.  
  66.     return 0;
  67. }
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement