제출 #541344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541344		keta_tsimakuridze	Cake 3 (JOI19_cake3)	C++14	24 / 100	4033 ms	57896 KiB

cake3

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"

const int N = 2e5 + 5, mod = 1e9 + 7; //!
int t, n,  ans = 0;
pii p[N];
int m;
int get(int sum, multiset<int> s, int a, int b) {
	int x = m;
	if(s.count(a) == 0) x--, sum += a;
	if(s.count(b) == (a == b)) x--, sum += b;
	
	while(s.size() > x) {
		sum -= *s.begin();
		s.erase(s.find(*s.begin()));
	}
	return sum;
	
}
void solve(int l,int r,int ql, int qr) {
	if(r < l) return;
	int mid = (l + r) >> 1, sum = 0;
	pii opt; opt = {-2e15, 0};
	multiset<int> s;
	for(int i = mid; i >= ql; i--) {
		s.insert(p[i].s); sum += p[i].s;
		if(s.size() == m + 1) {
			sum -= *s.begin();
			s.erase(s.find(*s.begin()));
		}
		
		if(s.size() >= m && i <= qr) {
			opt = max(opt, {sum - 2 * (p[mid].f - p[i].f), i});
		}
	}
	ans = max(ans, opt.f);
	if(l == r) return;
	solve(l, mid - 1, ql, opt.s); solve(mid + 1,r, opt.s, qr);
	
}
main() {
	ios_base::sync_with_stdio(false),
	cin.tie(0),cout.tie(0);
	cin >> n >> m;
	ans = -2e9;
	for(int i = 1; i <= n; i++) {
		cin >> p[i].s >> p[i].f;
	}
	sort(p + 1, p + n + 1);
	solve(m, n, 1, n - m + 1);
	cout << ans;
}

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'long long int get(long long int, std::multiset<long long int>, long long int, long long int)':
cake3.cpp:19:17: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   19 |  while(s.size() > x) {
      |                 ^
cake3.cpp: In function 'void solve(long long int, long long int, long long int, long long int)':
cake3.cpp:33:15: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   33 |   if(s.size() == m + 1) {
      |               ^
cake3.cpp:38:15: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |   if(s.size() >= m && i <= qr) {
      |               ^
cake3.cpp: At global scope:
cake3.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main() {
      | ^~~~

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