Submission #137902

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

cake3

#include <bits/stdc++.h>
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;
using namespace __gnu_pbds;
#define f first
#define s second
typedef long long ll;
typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, 
rb_tree_tag, tree_order_statistics_node_update> oset;
const int N = 2e5+5;
ll n, k, cur, ans, l;
pair<ll, ll> p[N];
oset s, tmp;
deque<ll> q;
int main()
{
	cin >> n >> k;
	for(int i=0; i<n; i++) cin >> p[i].s >> p[i].f;
	sort(p, p+n);
	for(int i=0; i<k; i++)
	{
		 if(i >= 1 && i < k-1) s.insert({p[i].s, i}), tmp.insert({i, p[i].s});
		 cur += p[i].s;
	}
	cur += p[0].f*2 - p[k-1].f*2;
	ans = max(cur, ans);
	for(int i=k; i<n; i++)
	{
		ll a = cur - p[i-1].s + p[i-1].f*2 + p[i].s - p[i].f*2;
		auto x = *tmp.find_by_order(0);
		ll idx = x.f;
		ll b = cur + p[i-1].f*2 + p[i].s - p[i].f*2 - p[l].s - p[l].f*2 + p[idx].f*2;
		x = *s.find_by_order(0);
		ll c = cur + p[i-1].f*2 + p[i].s - p[i].f*2 - x.f;
		if(a > b && a > c) cur = a;
		if(b > c && b > a)
		{
			x = *tmp.find_by_order(0);
			l = x.f;
			tmp.erase(x);
			s.erase({x.s, x.f});
			s.insert({p[i-1].s, i-1}), tmp.insert({i-1, p[i-1].s});
			cur = b;
		}
		if(c > a && c > b)
		{
			x = *s.find_by_order(0);
			s.erase(x), tmp.erase({x.s, x.f});
			s.insert({p[i-1].s, i-1}), tmp.insert({i-1, p[i-1].s});
			cur = c;
		}
		ans = max(ans, cur);
	}
	cout << ans << endl;
}

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