Submission #204364

#	Time	Username	Problem	Language	Result	Execution time	Memory
204364		ics0503	Cake 3 (JOI19_cake3)	C++17	0 / 100	5 ms	380 KiB

cake3

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
long long n, m, allSum = 0;
multiset<long long >L, R; // R is big
void balance() {
	if (L.size() == 0 || R.size() == 0)return;
	if (R.size() < m) {
		long long lmax = (*L.rbegin());
		L.erase(L.find(lmax)); R.insert(lmax);
		allSum += lmax;
		return;
	}
	long long lmax = (*L.rbegin()), rmin = (*R.begin());
	if (lmax > rmin) {
		L.erase(L.find(lmax)); R.erase(R.find(rmin));
		L.insert(rmin); R.insert(lmax);
		allSum += lmax - rmin;
	}
}
void add(long long x) {
	if (R.size() < m) { R.insert(x); allSum += x; }
	else L.insert(x);
	balance();
}
void del(long long x) {
	if (L.find(x) != L.end())L.erase(L.find(x));
	else { R.erase(R.find(x)); allSum -= x; }
	balance();
}
struct vc { long long v, c; }a[212121];
bool sort_c(vc a, vc b) {
	if (a.c != b.c)return a.c < b.c;
	return a.v > b.v;
}
long long SS[212121];
int main() {
	long long i, j, k; scanf("%lld%lld", &n, &m);
	for (i = 1; i <= n; i++) scanf("%lld%lld", &a[i].v, &a[i].c);
	sort(a + 1, a + n + 1, sort_c);
	for (i = 1; i <= n; i++)SS[i] = SS[i - 1] + a[i].v;
	for (i = 1; i <= m; i++)add(a[i].v);
	long long ans = allSum - 2ll * (a[m].c - a[1].c), s = 1;
	for (i = m + 1; i <= n; i++) {
		add(a[i].v);
		long long newRes = (SS[i] - SS[i - m]) - 2ll * (a[i].c - a[i - m + 1].c);
		long long nowRes = allSum - 2ll * (a[i].c - a[s].c);
		if (nowRes < newRes) {
			while (s < i - m + 1) {
				del(a[s].v);
				s++;
			}
		}
		while (i>=s+m) {
			long long befRes = allSum - 2ll * (a[i].c - a[s].c);
			del(a[s].v);
			long long nxtRes = allSum - 2ll * (a[i].c - a[s + 1].c);
			if (befRes <= nxtRes) s++;
			else {
				add(a[s].v);
				break;
			}
		}
		ans = max(ans, allSum - 2ll * (a[i].c - a[s].c));
	}
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void balance()':
cake3.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (R.size() < m) {
      ~~~~~~~~~^~~
cake3.cpp: In function 'void add(long long int)':
cake3.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (R.size() < m) { R.insert(x); allSum += x; }
      ~~~~~~~~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:39:15: warning: unused variable 'j' [-Wunused-variable]
  long long i, j, k; scanf("%lld%lld", &n, &m);
               ^
cake3.cpp:39:18: warning: unused variable 'k' [-Wunused-variable]
  long long i, j, k; scanf("%lld%lld", &n, &m);
                  ^
cake3.cpp:39:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long i, j, k; scanf("%lld%lld", &n, &m);
                     ~~~~~^~~~~~~~~~~~~~~~~~~~
cake3.cpp:40:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++) scanf("%lld%lld", &a[i].v, &a[i].c);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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