Submission #138920

#	Time	Username	Problem	Language	Result	Execution time	Memory
138920		Mahmoud_Adel	Cake 3 (JOI19_cake3)	C++14	0 / 100	6 ms	376 KiB

cake3

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
const int N = 1e5+5;
ll n, k, ans;
pair<ll, ll> p[N];
bool cmp(pair<ll, ll> a, pair<ll, ll> b)
{
	return a.s < b.s;
}
ll sum(ll l, ll r)
{
	vector<ll> vec;
	ll ret = 0;
	for(ll i=l; i<=r; i++)
	{
		vec.push_back(p[i].f);
	}
	sort(vec.rbegin(), vec.rend());
	for(ll i=0; i<k; i++) ret += vec[i];
	return ret;
}
void solve(ll l, ll r, ll s, ll e)
{
	assert(s <= e);
	if(l > r) return ;
	ll id = -1, m = -1e18;
	ll mid = (l+r)>>1;
	for(ll i=max(mid+k-1, (ll)s); i<=e; i++)
	{
		if(sum(mid, i) - (p[i].s-p[mid].s)*2LL > m) 
		m = sum(mid, i) - (p[i].s-p[mid].s)*2LL, id = i;
	}
	solve(l, mid-1, s, id);
	solve(mid+1, r, id, e);
	ans = max(ans, m);
}
	
int main()
{
	cin >> n >> k;
	for(int i=0; i<n; i++) cin >> p[i].f >> p[i].s;
	sort(p, p+n, cmp);
	solve(0, n-k, 0, n-1);
	cout << ans << endl;
}

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