Submission #113719

#	Time	Username	Problem	Language	Result	Execution time	Memory
113719		Mamnoon_Siam	Cake 3 (JOI19_cake3)	C++17	5 / 100	4099 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;
	for(int i = 1; i <= n; i++) {
		priority_queue<ll> Q;
		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]);
				ans = max(ans, S);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

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