fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e6 + 10;
  5.  
  6. class ConvexHull {
  7. private:
  8.     int head, tail;
  9.     long long A[N], B[N];
  10. public:
  11.     void init() { head = tail = 0; }
  12.     bool bad(int l1, int l2, int l3) {
  13.         return (long double) (B[l3] - B[l1]) / (A[l1] - A[l3]) < (long double) (B[l2] - B[l1]) / (A[l1] - A[l2]);
  14.     }
  15.     void add(long long a, long long b) {
  16.         A[tail] = a; B[tail++] = b;
  17.         while (tail > 2 && bad(tail - 3, tail - 2, tail - 1)) {
  18.             A[tail - 2] = A[tail - 1];
  19.             B[tail - 2] = B[tail - 1];
  20.             tail--;
  21.         }
  22.     }
  23.     long long query(long long x) {
  24.         if (head >= tail) head = tail - 1;
  25.         while (head < tail - 1
  26.                && A[head + 1] * x + B[head + 1] >= A[head] * x + B[head]) head++;
  27.         return A[head] * x + B[head];
  28.     }
  29. } hull;
  30.  
  31. int n, a, b, c;
  32. long long sum[N];
  33.  
  34. long long f(long long x) { return a * x * x + b * x + c; }
  35.  
  36. void load() {
  37.     scanf("%d%d%d%d", &n, &a, &b, &c);
  38.     for (int i = 1; i <= n; ++i) {
  39.         scanf("%lld", sum + i);
  40.         sum[i] += sum[i - 1];
  41.     }
  42. }
  43.  
  44. void process() {
  45.     hull.init();
  46.     long long cost = f(sum[1]);
  47.     hull.add(-2 * a * sum[1], cost + a * sum[1] * sum[1] - b * sum[1]);
  48.  
  49.     for (int i = 2; i <= n; ++i) {
  50.         cost = f(sum[i]) + max(0ll, hull.query(sum[i]));
  51.         hull.add(-2 * a * sum[i], cost + a * sum[i] * sum[i] - b * sum[i]);
  52.     }
  53.     printf("%lld\n", cost);
  54. }
  55.  
  56. int main() {
  57.   //  freopen("input.in", "r", stdin);
  58.  //   freopen("output.out", "w", stdout);
  59.  
  60.     int test; scanf("%d", &test);
  61.     while (test--) {
  62.         load();
  63.         process();
  64.     }
  65.  
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 39496KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/63g2fx
language:
C++14 (gcc 8.3)
created:
8 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!