AJPrakarn-T002: Aliens

#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) {};
};

#define f first
#define s second
typedef pair<int, int> pii;
typedef pair<linear, lli> pLl;

const int N = 4000 + 5;
const int K = 500 + 5;

deque<pLl> cht;
vector<pii> coor(1, pii(-1, -1));
lli dp[N][K];
pii tmp[N];

bool comp(const pii &lhs, const pii &rhs){
    if(lhs.f != rhs.f){
        return lhs.f < rhs.f;
    }
    return lhs.s > rhs.s;
}

lli intersect(linear a, linear b){
    lli x = b.c - a.c;
    lli y = a.m - b.m;
    return (lli)ceil((double)x / y);
}

void chtInsert(linear l){
    while(!cht.empty() && cht.back().f.m == l.m){
        if(cht.back().f.c > l.c){
            cht.pop_back();
            chtInsert(l);
        }
        return;
    }
    while(!cht.empty() && cht.back().s >= intersect(cht.back().f, l)){
        cht.pop_back();
    }
    if(cht.empty()){
        cht.emplace_back(l, 0);
    } else {
        cht.emplace_back(l, intersect(cht.back().f, l));
    }
}

lli chtQuery(lli x){
    while(cht.size() > 1 && next(cht.begin()) -> s <= x){
        cht.pop_front();
    }
    linear a = cht.front().f;
    return a.m * x + a.c;
}

int main(){

    int n, sz, parts;
    scanf("%d%d%d", &n, &sz, &parts);
    for(int i = 1; i <= n; ++i){
        scanf("%d%d", &tmp[i].f, &tmp[i].s);
        if(tmp[i].f > tmp[i].s){
            swap(tmp[i].f, tmp[i].s);
        }
    }
    sort(tmp + 1, tmp + n + 1, comp);
    for(int i = 1; i <= n; ++i){
        if(tmp[i].f >= coor.back().f && tmp[i].s <= coor.back().s){
            continue;
        }
        coor.push_back(tmp[i]);
    }
    n = (int)coor.size() - 1;
    for(int i = 1; i <= n; ++i){
        dp[i][0] = 1e18;
    }
    for(int p = 1; p <= parts; ++p){
        cht.clear();
        for(int i = 1; i <= n; ++i){
            lli camInter = max(0, coor[i - 1].s - coor[i].f + 1);
            chtInsert(linear(-2 * coor[i].f, (lli)coor[i].f * coor[i].f - 2 * coor[i].f - camInter * camInter + dp[i - 1][p - 1]));
            dp[i][p] = (lli)coor[i].s * coor[i].s + 2 * coor[i].s + 1 + chtQuery(coor[i].s);
        }
    }
    cout << dp[n][parts];

    return 0;
}