Submission #1000980

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#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;
}

ll main2() {
    memset(used, false, sizeof(used));
    ll ans = 0;
    if (n % 2 == 1) {
        // 演算子の優先順位には…気をつけようね！ 
        ans += (v[n-1].first+v[n-1].second)*(n/2);
        n--;
    }
    return ans + calc(n, n/2);
}

int main() {
    ios::sync_with_stdio(0);
    cout << setprecision(20);
    int nn;
    cin >> nn;
    n = nn;
    for (int i = 0; i < n; i++) {
        ll l, r;
        cin >> l >> r;
        v.push_back(P(l, r));
    }
    ll ans = TEN(18);
    sort(v.begin(), v.end(), [&](const P l, const P r){
        ll ls = l.first+l.second;
        ll rs = r.first+r.second;
        if (ls != rs) return ls > rs;
        return l.first > r.first;
    });
    ans = min(ans, main2());
    n = nn;
    sort(v.begin(), v.end(), [&](const P l, const P r){
        ll ls = l.first+l.second;
        ll rs = r.first+r.second;
        if (ls != rs) return ls > rs;
        return l.second > r.second;
    });

    ans = min(ans, main2());

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

Submission Info

Judge Result