Submission #1000901

---

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 n;
vector<P> v;

ll dp[MN][MN];
bool used[MN][MN];
ll calc(int m, int a) {
    if (m == 0) return 0;
    int b = n/2 - ((n-m)-(n/2-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);
    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);
    });
    ll ans = 0;
    if (n % 2 == 1) {
        ans += (v[n-1].first+v[n-1].second)*n/2;
        v.pop_back();
        n--;
    }

//    for (auto d: v) {
//        cout << d.first << " " << d.second << endl;
//    }
    cout << ans + calc(n, n/2) << endl;
    return 0;
}

Submission Info

Judge Result