Submission #2167633

---

Source Code Expand

#include <bits/stdc++.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}

using ll = long long;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

// Problem Specific Parameter:

#define fst first
#define snd second

ll dp[2510][2510][2];
ll L[5010], R[5010];

const ll inf = 1LL << 60;

int main(void) {
	int n;
	cin >> n;

	{
		using pll = pair<ll, ll>;
		vector<pll> ary;

		rep(i, n) {
			cin >> L[i] >> R[i];
			ary.push_back(pll(L[i] + R[i], L[i]));
		}

		sort(begin(ary), end(ary));

		rep(i, n) {
			L[i] = ary[i].snd;
			R[i] = ary[i].fst - L[i];
		}
	}

	rep(i, n / 2 + 1)rep(j, n / 2 + 1)rep(k, 2) dp[i][j][k] = inf;
	dp[0][0][0] = 0LL;

	const int m = n % 2;

	// cost = \sum  L_i  + \sum R_i

	rep(i, n) {
		rep(l, i + 1) {
			rep(k, m + 1) {
				const int r = i - l - k;
				if (l < 0 or l > n / 2) continue;
				if (r < 0 or r > n / 2) continue;

				// dp[l][r][k]

				// left
				if (l + 1 <= n / 2) {
					const ll add = (n / 2 - 1 - l) * (L[i] + R[i]) + R[i];
					chmin(dp[l + 1][r][k], dp[l][r][k] + add);
				}
				// right
				if (r + 1 <= n / 2) {
					const ll add = (n / 2 - 1 - r) * (L[i] + R[i]) + L[i];
					chmin(dp[l][r + 1][k], dp[l][r][k] + add);
				}
				// odd
				if (k + 1 <= m) {
					const ll add = (n - 1) * (L[i] + R[i]);
					chmin(dp[l][r][k + 1], dp[l][r][k] + add);
				}
			}
		}
	}

	cout << dp[n / 2][n / 2][m] << endl;

	return 0;
}

Submission Info

Judge Result