Submission #104722

#	Time	Username	Problem	Language	Result	Execution time	Memory
104722		Just_Solve_The_Problem	Cake 3 (JOI19_cake3)	C++11	24 / 100	4075 ms	12892 KiB

cake3

#include <bits/stdc++.h>

#define fr first
#define sc second
#define ll long long

using namespace std;

const int N = (int)2e5 + 7;

pair < ll, ll > ar[N];
int n, m;
ll pref[N], suf[N];

main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld", &ar[i].sc, &ar[i].fr);
	}
	sort(ar + 1, ar + n + 1);
	pref[0] = -1e18;
	for (int i = 1; i <= n; i++) {
		swap(ar[i].fr, ar[i].sc);
		pref[i] = max(pref[i - 1], ar[i].fr + 2 * ar[i].sc);
	}
	suf[n + 1] = -1e18;
	for (int i = n; i >= 1; i--) {
		suf[i] = max(suf[i + 1], ar[i].fr - 2 * ar[i].sc);
	}
	ll ans = -1e18;
	for (int l = 2; l <= n; l++) {
		multiset < int > s;
		ll sum = 0;
		for (int r = l; r < n; r++) {
			if (s.size() < m - 2) {
				sum += ar[r].fr;
				s.insert(ar[r].fr);
			} else {
				if (!s.empty() && ar[r].fr > *s.begin()) {
					sum -= *s.begin();
					sum += ar[r].fr;
					s.insert(ar[r].fr);
					s.erase(s.begin());
				}
			}
			if (s.size() == m - 2) {
				// cout << l << ' ' << r << ' ' << sum <<endl;
				ans = max(ans, sum + suf[r + 1] + pref[l - 1]);
			}
		}
	}
	cout << ans;
}

Compilation message (stderr)

cake3.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
cake3.cpp: In function 'int main()':
cake3.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (s.size() < m - 2) {
        ~~~~~~~~~^~~~~~~
cake3.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (s.size() == m - 2) {
        ~~~~~~~~~^~~~~~~~
cake3.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &ar[i].sc, &ar[i].fr);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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