Submission #113721

#	Time	Username	Problem	Language	Result	Execution time	Memory
113721		Mamnoon_Siam	Cake 3 (JOI19_cake3)	C++17	5 / 100	4022 ms	384 KiB

cake3

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

using ii = pair<int, int>;
using ll = long long;
const int maxn = 2e5 + 5;

int n, m;
int v[maxn], c[maxn];

int main(int argc, char const *argv[])
{
	// freopen("in", "r", stdin);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> v[i] >> c[i];
	}
	{
		vector<ii> tmp(n);
		for(int i = 0; i < n; i++) {
			tmp[i] = ii(c[i + 1], v[i + 1]);
		}
		sort(tmp.begin(), tmp.end());
		for(int i = 0; i < n; i++) {
			v[i + 1] = tmp[i].second;
			c[i + 1] = tmp[i].first;
		}
	}
	ll ans = LLONG_MIN;
	int last = 1;
	for(int i = 1; i + m - 1 <= n; i++) {
		priority_queue<ll> Q;
		int opt = -1;
		ll mn = LLONG_MIN;
		for(int j = i; j <= n; j++) {
			Q.push(v[j]);
			if(Q.size() >= m) {
				ll S = 0;
				vector<ll> tmp;
				while(tmp.size() < m) {
					S += Q.top();
					tmp.emplace_back(Q.top());
					Q.pop();
				}
				while(tmp.size()) {
					Q.push(tmp.back());
					tmp.pop_back();
				}
				S -= 2 * (c[j] - c[i]);
				if(mn <= S) {
					mn = S;
					opt = j;
				}
			}
		}
		ans = max(ans, mn);
		assert(last <= opt);
		last = opt;
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main(int, const char**)':
cake3.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(Q.size() >= m) {
       ~~~~~~~~~^~~~
cake3.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(tmp.size() < m) {
           ~~~~~~~~~~~^~~

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