Submission #376717

#	Time	Username	Problem	Language	Result	Execution time	Memory
376717		8e7	Cake 3 (JOI19_cake3)	C++14	24 / 100	23 ms	1900 KiB

cake3

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define ll long long
#define maxn 100005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

int n, m;
pii a[maxn];
inline bool cmp(pii a, pii b) {
	return a.ss < b.ss;
}

inline void ins(int l, int r, priority_queue<ll, vector<ll>, greater<ll> > & pq, ll & sum) {
	for (int i = l;i < r;i++) {
		sum += a[i].ff;
		pq.push(a[i].ff);
		if (pq.size() > m) {
			sum -= pq.top();
			pq.pop();
		}
	}
}

ll ans = -(1LL<<60);
void solve(int l, int r, int ql, int qr) {
	if (r <= l || qr <= ql) return;
	if (qr - ql == 1) {
		priority_queue<ll, vector<ll>, greater<ll> > pq;
		ll sum = 0;
		ins(ql, l, pq, sum);

		for (int i = l;i < r;i++) {
			ins(i, i + 1, pq, sum);
			//cout << i << " " << ql << " " << sum - 2 * (a[i].ss - a[ql].ss) << 0 << endl;
			ans = max(ans, sum - 2 * (a[i].ss - a[ql].ss));
		}
		return;
	}
	int mid = (l + r) / 2;
	ll best = -(1LL<<60), bind = 0;
	ll sum = 0;
	priority_queue<ll, vector<ll>, greater<ll> > pq;
	ins(min(qr, mid - m + 2), mid + 1, pq, sum);
	//cout << sum << endl;

	for (int i = min(qr - 1, mid - m + 1);i >= ql;i--) {
		ins(i, i + 1, pq, sum);
		ll val = sum - 2 * (a[mid].ss - a[i].ss);
		if (val > best) {
			best = val;
			bind = i;
		}
	}
	//cout << mid << " " << bind << " " << best << " " << 1 << endl;
	ans = max(ans, best);
	solve(l, mid, ql, bind + 1);
	solve(mid + 1, r, bind, qr);
}
int main() {
	io
	cin >> n >> m;
	for (int i = 0;i < n;i++) cin >> a[i].ff >> a[i].ss;
	sort(a, a + n, cmp);
	solve(m - 1, n, 0, n);
	cout << ans << "\n";
}
/*
5 3
2 1
4 2
6 4
8 8
10 16

8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879

 */

Compilation message (stderr)

cake3.cpp: In function 'void ins(int, int, std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >&, long long int&)':
cake3.cpp:25:17: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |   if (pq.size() > m) {
      |       ~~~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 0 / 76