SMMR-T159: Election Campaign

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1000;

int arr[N + 1];
lli dp[N + 1];

lli distance(int x, int y){
    int diff = x - y;
    return (lli)diff * diff;
}

int main(){

    int nVertex, carCost;
    scanf("%d%d", &nVertex, &carCost);
    for(int i = 1; i <= nVertex; ++i){
        scanf("%d", &arr[i]);
    }

    sort(arr + 1, arr + nVertex + 1);

    dp[0] = 0;
    for(int i = 1; i <= nVertex; ++i){
        lli mn = 1e18;
        for(int j = 1; j <= i; ++j){
            mn = min(mn, dp[j - 1] + distance(arr[i], arr[j]) + carCost);
        }
        dp[i] = mn;
    }
    cout << dp[nVertex];

    return 0;
}

// Convex Hull Trick Solution
#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

struct linear {
    lli m, c;
    linear(): m(0), c(0) {};
    linear(lli m, lli c): m(m), c(c) {};
};

const int N = 1000;

int arr[N + 1];
lli dp[N + 1];
deque<pair<linear, lli>> cht;

lli intersect(linear &a, linear &b){
    lli x = b.c - a.c;
    lli y = a.m - b.m;
    // ceiling of the answer
    return x / y + !(((x < 0) != (y < 0)) || (x % y == 0));
}

// Min CHT Insertion: Greater -> Less
void chtInsert(linear l){ // O(1) Insertion
    // new line has same m
    if(!cht.empty() && cht.back().first.m == l.m){
        if(cht.back().first.m > l.m){ // new line has lower c: less => better
            cht.pop_back();
            chtInsert(l);
        } // new line has higher c: greater => worse
        return;
    }
    // new line has left or same intersection but with lower m: less => better
    while(!cht.empty() && cht.back().second >= intersect(cht.back().first, l)){
        cht.pop_back();
    }
    // insert new line at the back
    if(cht.empty()){ // empty hull
        cht.emplace_back(l, 0);
    } else {
        cht.emplace_back(l, intersect(cht.back().first, l));
    }
}

// Min CHT Query: Less -> Greater
lli chtQuery(lli x){ // O(1) Query (Two Pointer)
    // upper_bound(cht.begin(), cht.end(), x) - 1
    while(cht.size() > 1 && next(cht.begin()) -> second <= x){
        cht.pop_front();
    }
    linear mn = cht.front().first;
    return mn.m * x + mn.c;
}

int main(){

    int nVertex, carCost;
    scanf("%d%d", &nVertex, &carCost);
    for(int i = 1; i <= nVertex; ++i){
        scanf("%d", &arr[i]);
    }

    dp[0] = 0;
    for(int i = 1; i <= nVertex; ++i){
        chtInsert(linear(-2 * arr[i], (lli)arr[i] * arr[i] + dp[i - 1]));
        dp[i] = carCost + (lli)arr[i] * arr[i] + chtQuery(arr[i]);
    }
    cout << dp[nVertex];

    return 0;
}