Submission #541343

#	Time	Username	Problem	Language	Result	Execution time	Memory
541343		keta_tsimakuridze	Cake 3 (JOI19_cake3)	C++14	0 / 100	2 ms	340 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(mid - i + 1 >= m) {
			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;
	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;
}

Compilation message (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: At global scope:
cake3.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main() {
      | ^~~~

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