Submission #362666

#	Time	Username	Problem	Language	Result	Execution time	Memory
362666		hoaphat1	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	364 KiB

cake3

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
  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;
  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 = 0;
  	long long now = 0;
  	priority_queue<int, vector<int>, greater<int>> pq;
  	for (int i = mid - 1; i > R; i--) now += a[i].second, pq.push(a[i].second);
  	long long val = 0;
  	for (int i = min(mid-1, R); i >= L; i--) {
  		if ((int) pq.size() == m - 2) {
  			if (val < now + a[i].second + 2 * a[i].first) {
  				val = now + a[i].second + 2 * a[i].first;
  				pos = i;
				}
			}
			pq.push(a[i].second);
			now += a[i].second;
			if ((int)pq.size() > m - 2) {
				now -= pq.top();
				pq.pop();
			}
		}
		ans = max(ans, val + a[mid].second - 2 * a[mid].first);
		solve(l, mid - 1, L, pos);
		solve(mid + 1, r, pos, R);
	};
  solve(m-1, n-1, 0, n-1);
  cout << ans;
} 

Compilation message (stderr)

cake3.cpp: In lambda function:
cake3.cpp:20:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |    int mid = l + r >> 1;
      |              ~~^~~

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