Submission #362678

#	Time	Username	Problem	Language	Result	Execution time	Memory
362678		hoaphat1	Cake 3 (JOI19_cake3)	C++17	100 / 100	1499 ms	38500 KiB

cake3

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
	#define qwer "test"
	if (fopen(qwer".inp","r")) freopen(qwer".inp","r",stdin),freopen(qwer".out","w",stdout);
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; i++) cin >> a[i].second >> a[i].first;
  sort(a.begin(), a.end());
  /*
  	k1 k2 ... km -> v - 2 * (c km - c k1)
  	i >= i-1
  */
  long long ans = -1e18;
  long long now = 0;
  int L = 0, R = -1;
  vector<int> kt(n, 0);
  priority_queue<pair<int, int>, vector<pair<int,int>> , greater<pair<int, int>>> pq;
  priority_queue<pair<int, int>> smaller;
  int sz = 0;
  auto add = [&](int id) {
  	int v = a[id].second;
  	pq.emplace(v, id);
  	now += v;
  	kt[id] = 1;
  	++sz;
  	while (sz > m - 2) {
  		auto x = pq.top();
  		pq.pop();
  		if (kt[x.second] != 1) continue;
  		kt[x.second] = 2;
  		now -= x.first;
  		smaller.push(x);
  		--sz;
		}
	};
	auto del = [&](int id) {
		int v = a[id].second;
		if (kt[id] == 2) {
			kt[id] = 0;
			return ;
		}
		kt[id] = 0;
		now -= v;
		sz--;
		while (sz < m - 2 && !smaller.empty()) {
			auto x = smaller.top(); smaller.pop();
			if (kt[x.second] != 2) continue;
			kt[x.second] = 1;
			now += x.first;
			pq.push(x);
			++sz;
		}
	};
  auto moveL = [&](int l) {
  	while (L < l) del(L++);
  	while (L > l) add(--L);
	};
	auto moveR = [&](int r) {
		while (R < r) add(++R);
		while (R > r) del(R--);
	};
  function<void(int, int, int, int)> solve = [&](int l, int r, int L, int R) {
  	if (l > r) return ;
  	int mid = l + r >> 1;
  	int pos = -1;
  	moveR(mid - 1);
  	long long val = 0;
  	for (int i = min(mid-1, R); i >= L; i--) {
  		moveL(i + 1);
  	///	cout << i + 1 <<" " << mid - 1 <<" " << now << endl;
  		if (sz == m - 2) {
  			if (val < now + a[i].second + 2 * a[i].first) {
  				val = now + a[i].second + 2 * a[i].first;
  				pos = i;
				}
			}
		}
		ans = max(ans, val + a[mid].second - 2 * a[mid].first);
		solve(mid + 1, r, pos, R);
		solve(l, mid - 1, L, pos);
	};
  solve(m-1, n-1, 0, n-1);
  cout << ans;
} 

Compilation message (stderr)

cake3.cpp: In lambda function:
cake3.cpp:70:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |    int mid = l + r >> 1;
      |              ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:7:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    7 |  if (fopen(qwer".inp","r")) freopen(qwer".inp","r",stdin),freopen(qwer".out","w",stdout);
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:7:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    7 |  if (fopen(qwer".inp","r")) freopen(qwer".inp","r",stdin),freopen(qwer".out","w",stdout);
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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