제출 #203365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203365		Noam527	Cake 3 (JOI19_cake3)	C++17	100 / 100	3394 ms	15100 KiB

cake3

#include <bits/stdc++.h>
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 4e18;
const int OO = 0;
const int OOO = 1;
using namespace std;

struct order {
	int m, newtime;
	ll sum;
	set<pair<int, int>> s;
	set<pair<int, int>>::iterator it;
	int stores;
	order() {}
	order(int M) {
		m = M;
		newtime = 0;
		sum = -1;

		s.insert({ -1, newtime++ });
		it = s.begin();
		stores = 1;
	}
	void fix() {
		while (stores < m) {
			if (it == s.begin()) break;
			--it;
			++stores;
			sum += it->first;
		}
		while (stores > m) {
			if (next(it) == s.end()) break;
			--stores;
			sum -= it->first;
			++it;
		}
	}
	void insert(int x) {
		s.insert({ x, newtime++ });
		if (it->first <= x) {
			stores++;
			sum += x;
		}
	}
	void erase(int x) {
		auto rit = s.lower_bound({ x, -1 });
		if (rit == it) {
			sum -= x;
			--it;
			sum += it->first;
			s.erase(rit);
			return;
		}
		if (x > it->first) {
			sum -= x;
			--stores;
			s.erase(rit);
			return;
		}
		s.erase(rit);
	}
	ll query() {
		fix();
		return sum;
	}
};

int n, m;
vector<pair<int, int>> a;
int L = 0, R = -1;
order S;

ll query(int l, int r) {
	if (r - l + 1 < m) return -inf;
	while (R < r)
		S.insert(a[++R].first);
	while (L < l)
		S.erase(a[L++].first);
	while (l < L)
		S.insert(a[--L].first);
	while (r < R)
		S.erase(a[R--].first);
	return S.query();
}

ll calc(int st, int en, int optl, int optr) {
	en = min(en, optr - m + 1);
	if (st > en) return -inf;
	if (OO) {
		cout << "at calc(" << st << ", " << en << ", " << optl << ", " << optr << ")\n";
	}
	int mid = (st + en) / 2;
	
	int at = -1;
	ll mx = -inf;
	for (int i = max(mid, optl); i <= optr; i++) {
		ll res = query(mid, i) - 2 * (a[i].second - a[mid].second);
		if (mx < res) {
			mx = res;
			at = i;
		}
	}
	if (OO) {
		cout << "the best for " << mid << " is " << at << ", with worth " << mx << '\n';
	}
	mx = max(mx, calc(st, mid - 1, optl, at));
	mx = max(mx, calc(mid + 1, en, at, optr));
	return mx;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	a.resize(n);
	S = order(m);

	for (auto &i : a) cin >> i.first >> i.second;
	sort(a.begin(), a.end(), [](const pair<int, int> &aa, const pair<int, int> &bb) {
		return aa.second < bb.second;
	});
	cout << calc(0, n - 1, 0, n - 1) << '\n';
}

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