Submission #106177

#	Time	Username	Problem	Language	Result	Execution time	Memory
106177		mzhao	Cake 3 (JOI19_cake3)	C++11	24 / 100	246 ms	604 KiB

cake3

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

#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif

#define MN 200100
#define x first
#define y second

using ll = long long;

int N, M;
pair<ll, ll> A[MN];
ll ans = -1e17;

bool cmp(pair<ll, ll> a, pair<ll, ll> b) {
	if (a.y == b.y) return a.x > b.x;
	return a.y > b.y;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	assert(N <= 2000);
	for (int i = 0; i < N; i++) {
		cin >> A[i].x >> A[i].y;
	}
	sort(A, A+N, cmp);
	ll pos = 0;
	for (int i = M-1; i < N; i++) {
		multiset<ll> cur;
		ll tot = 0;
		ll bestscore = -1e17;
		ll bestpos;
		for (int j = i; j >= 0; j--) {
			tot += A[j].x;
			cur.insert(A[j].x);
			if (cur.size() > M) {
				tot -= *cur.begin();
				cur.erase(cur.begin());
			}
			if (cur.size() == M) {
				ll score = tot-2*(A[j].y-A[i].y);
				if (score > bestscore) {
					bestscore = score;
					bestpos = j;
				}
			}
		}
		assert(bestpos >= pos);
		pos = bestpos;
		ans = max(ans, bestscore);
	}
	cout << ans << "\n";
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (cur.size() > M) {
        ~~~~~~~~~~~^~~
cake3.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (cur.size() == M) {
        ~~~~~~~~~~~^~~~

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