fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5.  
  6. const int MAX = 2e5 + 5;
  7.  
  8. struct line {
  9.     int a, b;
  10.  
  11.     line(int a = 0, int b = 0) : a(a), b(b) {};
  12.  
  13.     int operator () (const int &x) const {
  14.         return a * x + b;
  15.     }
  16. };
  17.  
  18. namespace CHT {
  19.     line lines[MAX];
  20.     int l = 0, r = -1;
  21.  
  22.     double insect(line &x, line &y) {
  23.         return 1.0 * (y.b - x.b) / (x.a - y.a);
  24.     }
  25.  
  26.     void add(line newline) {
  27.         while (l <= r && r - l + 1 > 1 && insect(newline, lines[r]) <= insect(newline, lines[r - 1])) --r;
  28.         lines[++r] = newline;
  29.     }
  30.  
  31.     int get(int x) {
  32.         while (l <= r && r - l + 1 > 1 && lines[l](x) > lines[l + 1](x)) ++l;
  33.         return lines[l](x);
  34.     }
  35. };
  36.  
  37. int h[MAX], f[MAX];
  38. int32_t main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr);
  41. //    freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout);
  42.     int n, c;
  43.     cin >> n >> c;
  44.     for (int i = 1; i <= n; i++) cin >> h[i];
  45.  
  46.     f[1] = 0;
  47.     CHT::add(line(-2 * h[1], f[1] + h[1] * h[1]));
  48.     for (int i = 2; i <= n; i++) {
  49.         f[i] = CHT::get(h[i]) + h[i] * h[i] + c;
  50.         CHT::add(line(-2 * h[i], f[i] + h[i] * h[i]));
  51.     }
  52.  
  53.     cout << f[n];
  54.     return 0;
  55. }
  56.  
Success #stdin #stdout 0.01s 7400KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/gvvrGT
language:
C++14 (gcc 8.3)
created:
11 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!