Submission #1001186

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }
 
const int MN = 5050;
using P = pair<ll, ll>;
int X;
vector<P> v;
 
ll dp[MN][MN];
bool used[MN][MN];
ll calc(int m, int a) {
    if (m == 0) return 0;
    int b = m-a;
    if (used[m][a]) return dp[m][a];
    used[m][a] = true;
    ll &ans = dp[m][a];
    ans = TEN(18);
    P p = v[m-1];
    // left
    if (a) { 
        ll x = p.first*(a-1);
        x += p.second*(a);
        ans = min(ans, x + calc(m-1, a-1));
    }
    // right
    if (b) {
        ll x = p.first*(b);
        x += p.second*(b-1);
        ans = min(ans, x + calc(m-1, a));
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cout << setprecision(20);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        ll l, r;
        cin >> l >> r;
        v.push_back(P(l, r));
    }
    sort(v.begin(), v.end(), [&](const P l, const P r){
        return (l.first+l.second) > (r.first+r.second);
    });
    if (n % 2 == 0) {
        X = n;
        cout << calc(n, n/2) << endl;
        return 0;
    }

    ll L = v.back().first+v.back().second;
    X = 0;
    for (int i = n-1; i >= 0; i--) {
        if (v[i].first+v[i].second > L) {
            X = i+1;
            break;
        }
    }

    int U = n-X;
    sort(v.begin()+X, v.end(), [&](const P l, const P r){
        return l.second < r.second;
    });

    vector<ll> fsm(U+1), ssm(U+1), osm(U+1);
    fsm[0] = ssm[0] = 0;
    osm[0] = 0;
    for (int i = 0; i < U; i++) {
        fsm[i+1] = fsm[i]+v[X+i].first;
        ssm[i+1] = ssm[i]+v[X+i].second;
        osm[i+1] = osm[i]+i;
    }

    ll ans = TEN(18);
    int m = (n-1)/2;
    for (int i = 0; i <= U; i++) {
        int j = U-i-1;
        if (m-i < 0 || X-(m-i) < 0) continue;
        ll base = calc(X, m-i);
        base += ssm[i];
        base += fsm[U]-fsm[U-j];
        base += L * m;
        base += L * min(TEN(18)/L, (ll(i+j)*m - (osm[i+1]+osm[j+1])));
        ans = min(ans, base);
    }

    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result