Submission #105017

#	Time	Username	Problem	Language	Result	Execution time	Memory
105017		YottaByte	Cake 3 (JOI19_cake3)	C++14	0 / 100	4 ms	384 KiB

cake3

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

#define int long long
#define fr first
#define sc second
#define pii pair < int, int >

const int N = 4001;

int n, k;
long long ans = -1e18;
pii a[N];
set < int > s;

bool cmp(pii a, pii b) {
	if(a.sc < b.sc) return true;
	else if(a.sc == b.sc) return (a.fr < b.fr);
	else return false;
}

main() {
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++)
		cin >> a[i].fr >> a[i].sc;
	
	sort(a + 1, a + n + 1, &cmp);
	
	long long res = 0;
	for(int i = 1; i <= n; i++) {
		res = a[i].fr;
		while(s.size()) {
			s.erase(s.begin());
		}
		for(int j = i + 1; j <= n; j++) {
			res += a[j].fr;
			if(s.size() > k - 2) {
				res -= *s.begin();
				s.erase(s.begin());
			}
			
			if(s.size() == k - 2)
				ans = max(res - 2ll * (a[j].sc - a[i].sc), ans);
			
			s.insert( a[j].fr );
		}
	}
	
	cout << ans << endl;
}
/***
5 3
2 1
4 2
6 4
8 8
10 16
***/

Compilation message (stderr)

cake3.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
cake3.cpp: In function 'int main()':
cake3.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(s.size() > k - 2) {
       ~~~~~~~~~^~~~~~~
cake3.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(s.size() == k - 2)
       ~~~~~~~~~^~~~~~~~

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