fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5 + 5;
  5.  
  6. // from kactl
  7.  
  8. struct Line {
  9. 	mutable long long k, m, p;
  10. 	bool operator<(const Line& o) const { return k < o.k; }
  11. 	bool operator<(long long x) const { return p < x; }
  12. };
  13.  
  14. struct LineContainer : multiset<Line, less<>> {
  15. 	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
  16. 	const long long inf = LLONG_MAX;
  17. 	long long div(long long a, long long b) { // floored division
  18. 		return a / b - ((a ^ b) < 0 && a % b); 
  19. 	}
  20. 	bool isect(iterator x, iterator y) {
  21. 		if (y == end()) { x->p = inf; return false; }
  22. 		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
  23. 		else x->p = div(y->m - x->m, x->k - y->k);
  24. 		return x->p >= y->p;
  25. 	}
  26. 	void add(long long k, long long m) {
  27. 		auto z = insert({k, m, 0}), y = z++, x = y;
  28. 		while (isect(y, z)) z = erase(z);
  29. 		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
  30. 		while ((y = x) != begin() && (--x)->p >= y->p)
  31. 			isect(x, erase(y));
  32. 	}
  33. 	long long query(long long x) {
  34. 		assert(!empty());
  35. 		auto l = *lower_bound(x);
  36. 		return l.k * x + l.m;
  37. 	}
  38. };
  39.  
  40. long long c;
  41. int n;
  42.  
  43. int arr[N];
  44. long long dp[N];
  45. LineContainer hull;
  46. int hullIt;
  47.  
  48. void read() {
  49.   scanf("%d %lld", &n, &c);
  50.   for (int i = 1; i <= n; i++) {
  51.     scanf("%d", &arr[i]);
  52.   }
  53. }
  54.  
  55. void add(long long k, long long m) {
  56.   hull.add(k, m);
  57. }
  58.  
  59. long long extract(long long x) {
  60.   return hull.query(x);
  61. }
  62.  
  63. void work2() {
  64.   for (int i = 2; i <= n; i++) {
  65.     int best = -1;
  66.     long long val = 4e18;
  67.  
  68.     for (int j = 1; j < i; j++) {
  69.       long long cur = 1ll * (arr[i] - arr[j]) * (arr[i] - arr[j]) + dp[j] + c;
  70.       if (cur < val) {
  71.         val = cur;
  72.         best = j;
  73.       }
  74.     }
  75.  
  76.     dp[i] = val;
  77.     printf("%d: best %d dp %lld\n", i, best, dp[i]);
  78.   }
  79. }
  80.  
  81. long long work() {
  82.   dp[1] = 0;
  83.  
  84.   add(2 * arr[1], dp[1] - 1ll * arr[1] * arr[1] - c);
  85.  
  86.   for (int i = 2; i <= n; i++) {
  87.     dp[i] = extract(arr[i]) - 1ll * arr[i] * arr[i];
  88.     // printf("i %d dp %lld\n", i, dp[i]);
  89.     add(2 * arr[i], dp[i] - 1ll * arr[i] * arr[i] - c);
  90.   }
  91.  
  92.   return -dp[n];
  93. }
  94.  
  95. int main() {
  96.   read();
  97.   // work2();
  98.   cout << work() << endl;
  99.   return 0;
  100. }
Success #stdin #stdout 0s 17584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/wN5kyR
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!