Submission #362673

#	Time	Username	Problem	Language	Result	Execution time	Memory
362673		hoaphat1	Cake 3 (JOI19_cake3)	C++17	24 / 100	4042 ms	10808 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;
  multiset<int> pq;
  multiset<int> smaller;
  long long now = 0;
  int L = 0, R = -1;
  auto add = [&](int v) {
  	pq.insert(v);
  	now += v;
  	if (pq.size() > m - 2) {
  		smaller.insert(*pq.begin());
  		now -= *pq.begin();
  		pq.erase(pq.begin());
		}
	};
	auto del = [&](int v) {
		auto it = pq.find(v);
		if (it != pq.end()) {
			now -= *it;
			pq.erase(it);
			if (!smaller.empty()) {
				pq.insert(*prev(smaller.end()));
				now += *prev(smaller.end());
				smaller.erase(prev(smaller.end()));
			}
		}
		else {
			smaller.erase(smaller.find(v));
		}
	};
  auto moveL = [&](int l) {
  	while (L < l) del(a[L++].second);
  	while (L > l) add(a[--L].second);
	};
	auto moveR = [&](int r) {
		while (R < r) add(a[++R].second);
		while (R > r) del(a[R--].second);
	};
  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);
  		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;
				}
			}
		}
		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:27:18: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |    if (pq.size() > m - 2) {
      |        ~~~~~~~~~~^~~~~~~
cake3.cpp: In lambda function:
cake3.cpp:58:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |    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: 0 / 76