Submission #204350

#	Time	Username	Problem	Language	Result	Execution time	Memory
204350		ics0503	Cake 3 (JOI19_cake3)	C++17	0 / 100	5 ms	256 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;
}
int main() {
	long long i, j; scanf("%lld%lld", &n, &m);
	for (i = 0; i < n; i++) scanf("%lld%lld", &a[i].v, &a[i].c);
	sort(a, a + n, sort_c);
	for (i = 0; i < m; i++)add(a[i].v);
	long long ans = allSum - 2 * (a[m - 1].c - a[0].c);
	long long s = 0;
	for (i = m; i < n; i++) {
		add(a[i].v);
		while (i>=s+m) {
			long long befSum = allSum;
			del(a[s].v);
			long long nxtSum = allSum;
			if (befSum - 2 * (a[i].c - a[s].c) <= nxtSum - 2 * (a[i].c - a[s + 1].c)) s++;
			else {
				add(a[s].v);
				break;
			}
		}
		ans = max(ans, allSum - 2 * (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:38:15: warning: unused variable 'j' [-Wunused-variable]
  long long i, j; scanf("%lld%lld", &n, &m);
               ^
cake3.cpp:38:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long i, j; scanf("%lld%lld", &n, &m);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~
cake3.cpp:39:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < n; i++) scanf("%lld%lld", &a[i].v, &a[i].c);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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