Submission #167317

#	Time	Username	Problem	Language	Result	Execution time	Memory
167317		maruii	Cake 3 (JOI19_cake3)	C++14	24 / 100	110 ms	632 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pli = pair<long long, int>;
#define ff first
#define ss second

int N, M;
vector<pii> P, xx;
const int SIZE = 1 << 11;
struct ST {
	pli A[2 * SIZE];
	void update(int x, pli v) {
		x += SIZE; A[x] = v;
		for (x >>= 1; x; x >>= 1) {
			A[x].ff = A[x << 1].ff + A[x << 1 | 1].ff;
			A[x].ss = A[x << 1].ss + A[x << 1 | 1].ss;
		}
	}
	long long query(int v) {
		int x = 1;
		long long ret = 0;
		while (x < SIZE) {
			if (A[x << 1 | 1].ss >= v) x = x << 1 | 1;
			else {
				x <<= 1;
				ret += A[x | 1].ff;
				v -= A[x | 1].ss;
			}
		}
		return ret + A[x].ff;
	}
} seg;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	if (N > 2000) assert(0);
	for (int i = 0; i < N; ++i) {
		int x, y; cin >> y >> x;
		P.emplace_back(x, y);
	}
	sort(P.begin(), P.end());
	for (int i = 0; i < N; ++i) xx.emplace_back(P[i].ss, i);
	sort(xx.begin(), xx.end());
	for (int i = 0; i < N; ++i) P[i].ss = lower_bound(xx.begin(), xx.end(), pii(P[i].ss, i)) - xx.begin();
	long long ans = -1e18;
	for (int i = 0; i < P.size(); ++i) {
		for (int j = i; j < P.size(); ++j) {
			seg.update(P[j].ss, pii(xx[P[j].ss].ff, 1));
			if (j - i + 1 >= M) ans = max(ans, seg.query(M) - 2 * (P[j].ff - P[i].ff));
		}
		memset(seg.A, 0, sizeof(seg.A));
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < P.size(); ++i) {
                  ~~^~~~~~~~~~
cake3.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i; j < P.size(); ++j) {
                   ~~^~~~~~~~~~

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