Submission #362667

#	Time	Username	Problem	Language	Result	Execution time	Memory
362667		hoaphat1	Cake 3 (JOI19_cake3)	C++17	24 / 100	4051 ms	11188 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
  */
  auto work = [&]() {
  	long long ans = -1e18;
  	for (int i = 0; i < n; i++) {
  		priority_queue<int, vector<int> ,greater<int>> pq;
  		long long now = 0;
  		for (int j = i + 1; j < n; j++) {
  			if (pq.size() == m - 2) {
  				ans = max(ans, now + a[j].second + a[i].second - 2 * (a[j].first - a[i].first));
				}
				now += a[j].second;
				pq.push(a[j].second);
				if (pq.size() > m - 2) {
					now -= pq.top();
					pq.pop();
				}
			}
		}
		cout << ans << endl;
	};
  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);
  work();
  ///cout << ans;
} 

Compilation message (stderr)

cake3.cpp: In lambda function:
cake3.cpp:23:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |      if (pq.size() == m - 2) {
      |          ~~~~~~~~~~^~~~~~~~
cake3.cpp:28:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |     if (pq.size() > m - 2) {
      |         ~~~~~~~~~~^~~~~~~
cake3.cpp: In lambda function:
cake3.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |    int mid = l + r >> 1;
      |              ~~^~~

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