Submission #1277869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277869		mingga	Cake 3 (JOI19_cake3)	C++20	100 / 100	1289 ms	12696 KiB

cake3

// Author: caption_mingle
#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define ll long long
const int mod = 1e9 + 7;
const int inf = 2e9;

const int N = 2e5 + 7;
int n, m;
pair<int, int> d[N];

vector<int> vec;
pair<ll, int> st[N * 4];
ll dp[N];

pair<ll, int> merge(pair<ll, int> x, pair<ll, int> y) {
	return make_pair(x.fi + y.fi, x.se + y.se);
}

void update(int i, int l, int r, int u, int x) {
	if(l > u or r < u) return;
	if(l == r) {
		st[i].fi += 1ll * x * vec[l - 1];
		st[i].se += x;
		return;
	}
	int m = (l + r) >> 1;
	update(i * 2, l, m, u, x);
	update(i * 2 + 1, m + 1, r, u, x);
	st[i] = merge(st[i * 2], st[i * 2 + 1]);
}

ll walk(int i, int l, int r, int k) {
	if(l == r) {
		return 1ll * k * vec[l - 1];
	}
	int m = (l + r) >> 1;
	if(st[i * 2 + 1].se >= k) {
		return walk(i * 2 + 1, m + 1, r, k);
	}
	return st[i * 2 + 1].fi + walk(i * 2, l, m, k - st[i * 2 + 1].se);
}

ll get(int i, int l, int r, int u) {
	if(l == r) return st[i].fi;
	int m = (l + r) >> 1;
	if(u <= m) return get(i * 2, l, m, u);
	return get(i * 2 + 1, m + 1, r, u);
}

int lb = 1, rb = 0;

void add(int x) {
	update(1, 1, sz(vec), d[x].se, 1);
}
void rem(int x) {
	update(1, 1, sz(vec), d[x].se, -1);
}

void move(int l1, int r1) {
	while(lb < l1) rem(lb++);
	while(lb > l1) add(--lb);
	while(rb < r1) add(++rb);
	while(rb > r1) rem(rb--);
}

void solve(int l, int r, int optl, int optr) {
	if(l > r) return;
	int mid = (l + r) >> 1;
	move(optl, mid - 1);
	int best = optl;
	for(int i = optl; i <= min(optr, mid - m + 1); i++) {
		move(i + 1, mid - 1);
		ll cur = walk(1, 1, sz(vec), m - 2) + vec[d[i].se - 1] + vec[d[mid].se - 1] - 2ll * (d[mid].fi - d[i].fi);
		if(cur > dp[mid]) {
			dp[mid] = cur;
			best = i;
		}
	}
	solve(l, mid - 1, optl, best);
	solve(mid + 1, r, best, optr);
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		int v, c; cin >> v >> c;
		vec.pb(v);
		d[i] = {c, v};
	}
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	sort(d + 1, d + n + 1);
	for(int i = 1; i <= n; i++) {
		d[i].se = upper_bound(all(vec), d[i].se) - vec.begin();
	}
	memset(dp, -0x3f, sizeof dp);
	solve(1, n, 1, n);
	cout << * max_element(dp + 1, dp + n + 1);
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:96:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:97:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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