F - Intervals
Time limit : 2sec / Memory limit : 256MB

Score : 1000 points

Problem Statement
Snuke received N intervals as a birthday present. The i-th interval was [−Li,Ri]. It is guaranteed that both Li and Ri are positive. In other words, the origin is strictly inside each interval.

Snuke doesn't like overlapping intervals, so he decided to move some intervals. For any positive integer d, if he pays d dollars, he can choose one of the intervals and move it by the distance of d. That is, if the chosen segment is [a,b], he can change it to either [a+d,b+d] or [a−d,b−d].

He can repeat this type of operation arbitrary number of times. After the operations, the intervals must be pairwise disjoint (however, they may touch at a point). Formally, for any two intervals, the length of the intersection must be zero.

Compute the minimum cost required to achieve his goal.

Constraints
1≤N≤5000
1≤Li,Ri≤109
All values in the input are integers.

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 5005;
const long long inf = (1LL<<62);

int i, j, n, k, curr;
struct interval
{
    int l, r, len;
    bool operator < (const interval &other) const
    {
        return len > other.len;
    }
} a[Nmax];
long long d[Nmax/2][Nmax/2][2], ans;

int main()
{
    //freopen("intervals.in", "r", stdin);
    //freopen("intervals.out", "w", stdout);

    scanf("%d", &n);
    for(i=1; i<=n; ++i) scanf("%d%d", &a[i].l, &a[i].r), a[i].len = a[i].l + a[i].r;

    if(n%2==0) ++n;
    sort(a+1, a+n+1);

    for(i=0; i<=n/2; ++i)
    for(j=0; j<=n/2; ++j)
        d[i][j][0] = d[i][j][1] = inf;

    d[0][0][0] = 0;

    for(i=0; i<=n/2; ++i)
    for(j=0; j<=n/2; ++j)
    for(k=0; k<=1; ++k)
    {
        curr = i+j+k+1;
        if(curr>n) continue;

        if(i<n/2) d[i+1][j][k] = min(d[i+1][j][k], d[i][j][k] + a[curr].r + 1LL*a[curr].len*i);
        if(j<n/2) d[i][j+1][k] = min(d[i][j+1][k], d[i][j][k] + a[curr].l + 1LL*a[curr].len*j);
        if(!k) d[i][j][1] = min(d[i][j][1], d[i][j][0] + 1LL*(n-1)/2*a[curr].len);
    }

    printf("%lld\n", d[n/2][n/2][1]);

    return 0;
}