題意使用 openssl enc -aes256 -pbkdf2 加密。

U2FsdGVkX1/pFyM6ex65XOnzO7af9rPopCTtRVWnqjbCrXGBrNoshbyxGeHvil2s
n6+XriANCfQ/bRPUjDlwt9Slm4EBsOr/2Fphwl0URvUKufnhA0SZrKjWu2zqe0ts
70q41Zz3/3XS/uXY9pV/54Ryc3jXUqIFQ7wFY66DwjAyk5Qy1Fa58IL8trJN9mod
y+s10tm4Vr98vwLYn5tKkQlxc8fYwk1lXCoSRHwgFOEey1aadDRXeeETpWehQq6Q
yx7FFhuF4zS4ZvHOV1+VZ3V5noIyt0ekyN4Q+5hb/zNPPRJ5YjggF5eE7s6YghvP

解析

貢獻的計算式子可以轉化成：max⁡{ri−lj,rj−li}\max\left\{r_i - l_j, r_j - l_i\right\}。也就是說對於每一個配對正好有一個貢獻為 +r+r，一個貢獻為 −l-l，對於所有二元組就是恰好有一半貢獻為 +r+r，其他為 −l-l。於是考慮貪心，先假設全部貢獻 +r+r，在減去 r+lr+l 的前 n2\frac{n}{2} 小的和。

int main()
{
	int n;
	scanf("%d", &n);
	std::vector<std::pair<int, int>> a(n);
	for (auto &[l, r] : a) scanf("%d%d", &l, &r);

	long long ans = 0;
	for (auto [_, r] : a) ans += r;

	std::vector<long long> lr;
	for (auto [l, r] : a) lr.emplace_back(l + r);
	std::sort(lr.begin(), lr.end());

	for (int i = 0; i < n / 2; i++) {
		ans -= lr[i];
	}

	printf("%lld\n", ans);
}