Submission #2167598


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

				// 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

Submission Time
Task F - Intervals
User Hec
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2269 Byte
Status WA
Exec Time 145 ms
Memory 98736 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1000
Status
AC × 2
AC × 41
WA × 4
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 143 ms 98608 KB
001.txt AC 33 ms 42368 KB
002.txt AC 142 ms 98608 KB
003.txt WA 114 ms 86332 KB
004.txt AC 142 ms 98608 KB
005.txt WA 64 ms 61184 KB
006.txt AC 143 ms 98608 KB
007.txt AC 77 ms 69504 KB
008.txt AC 143 ms 98608 KB
009.txt AC 16 ms 29824 KB
010.txt AC 143 ms 98608 KB
011.txt AC 66 ms 63360 KB
012.txt AC 143 ms 98608 KB
013.txt AC 14 ms 25600 KB
014.txt AC 141 ms 98608 KB
015.txt WA 33 ms 42368 KB
016.txt AC 142 ms 98608 KB
017.txt AC 111 ms 86332 KB
018.txt AC 144 ms 98736 KB
019.txt WA 77 ms 67456 KB
020.txt AC 1 ms 256 KB
021.txt AC 1 ms 256 KB
022.txt AC 129 ms 98608 KB
023.txt AC 142 ms 98608 KB
024.txt AC 145 ms 98608 KB
025.txt AC 142 ms 98608 KB
026.txt AC 141 ms 98608 KB
027.txt AC 142 ms 98608 KB
028.txt AC 142 ms 98608 KB
029.txt AC 141 ms 98608 KB
030.txt AC 141 ms 98608 KB
031.txt AC 141 ms 98608 KB
032.txt AC 140 ms 98608 KB
033.txt AC 142 ms 98608 KB
034.txt AC 142 ms 98608 KB
035.txt AC 141 ms 98608 KB
036.txt AC 143 ms 98608 KB
037.txt AC 142 ms 98608 KB
038.txt AC 141 ms 98608 KB
039.txt AC 141 ms 98608 KB
040.txt AC 141 ms 98608 KB
041.txt AC 143 ms 98608 KB
042.txt AC 143 ms 98608 KB
example0.txt AC 1 ms 256 KB
example1.txt AC 1 ms 256 KB