제출 #362669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362669		hoaphat1	Cake 3 (JOI19_cake3)	C++17	24 / 100	4074 ms	6680 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 = -1;
  	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);
			if ((int)pq.size() > m - 2) now -= pq.top(), pq.pop();
		}
  	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);
		//cout << l <<" " << r <<" " << mid <<" " << L <<" " << R << endl;
		assert(pos != -1);
		solve(l, mid - 1, L, pos);
		solve(mid + 1, r, pos, R);
	};
  solve(m-1, n-1, 0, n-1);
  ///work();
  cout << ans;
} 

컴파일 시 표준 에러 (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;
      |              ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:17:8: warning: variable 'work' set but not used [-Wunused-but-set-variable]
   17 |   auto work = [&]() {
      |        ^~~~

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