Submission #104807

#	Time	Username	Problem	Language	Result	Execution time	Memory
104807		Just_Solve_The_Problem	Cake 3 (JOI19_cake3)	C++11	0 / 100	233 ms	263168 KiB

cake3

#include <bits/stdc++.h>

#define fr first
#define sc second
#define ll long long
#define ok puts("ok");

using namespace std;

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

pair < ll, ll > ar[N];
int n, m;
ll pref[N], suf[N];
ll ans;
int siz = 1;
int root[N];

struct node {
	int l, r;
	ll sum;
	int cnt;
	node() {
		l = r = 0;
		sum = 0;
		cnt = 0;
	}
};
node tree[N * 100];

void build(int v = 1, int l = 1, int r = n) {
	if (l == r) {
		return ;
	}
	int mid = (l + r) >> 1;
	tree[v].l = ++siz;
	tree[v].r = ++siz;
	build(tree[v].l, l, mid);
	build(tree[v].r, mid + 1, r);
}

void upd(int ov, int nv, int pos, int val, int l = 1, int r = n) {
	if (l == r) {
		tree[nv].sum += val;
		tree[nv].cnt++;
		return ;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) {
		tree[nv].l = ++siz;
		tree[nv].r = tree[ov].r;
		upd(tree[ov].l, tree[nv].l, pos, val, l, mid);
	} else {
		tree[nv].l = tree[ov].l;
		tree[nv].r = ++siz;
		upd(tree[ov].r, tree[nv].r, pos, val, mid + 1, r);
	}
	tree[nv].sum = tree[tree[nv].l].sum + tree[tree[nv].r].sum;
	tree[nv].cnt = tree[tree[nv].l].cnt + tree[tree[nv].r].cnt;
}

ll getsum(int lv, int rv, int l = 1, int r = n, int keep = m - 2) {
	if (keep == 0) return 0;
	if (keep >= tree[rv].cnt - tree[lv].cnt) {
		return tree[rv].sum - tree[lv].sum;
	} else {
		if (l == r) {
			return (tree[rv].sum - tree[lv].sum) / (tree[rv].cnt - tree[lv].cnt) * keep;
		}
	}
	ll res = 0;
	int mid = (l + r) >> 1;
	return getsum(tree[lv].l, tree[rv].l, l, mid, max(keep - (tree[tree[rv].r].cnt - tree[tree[lv].r].cnt), 0)) + getsum(tree[lv].r, tree[rv].r, mid + 1, r, keep);
}

ll get(ll l, ll r) {
	return getsum(root[l - 1], root[r]);
}

void make(int l, int r, int optl, int optr) {
	if (l > r) return ;
	int mid = (l + r) >> 1;
	int opt = min(mid + m - 1, optr);
	ll res = -1e18;
	for (int i = max(mid + m - 1, optl); i <= optr; i++) {
		ll cost = get(mid + 1, i - 1) + pref[mid] + suf[i];
		if (cost > res) {
			res = cost;
			opt = i;
		}
	}
	// cout << mid << ' ' << res << ' ' << opt << endl;
	if (res > ans) {
		ans = res;
	}
	make(l, mid - 1, optl, opt);
	make(mid + 1, r, opt, optr);
}

void solve() {
	build();
	root[0] = 1;
	vector < int > vx;
	int asd[N];
	for (int i = 1; i <= n; i++) {
		vx.push_back(ar[i].fr);
	}
	sort(vx.begin(), vx.end());
	vx.resize(unique(vx.begin(), vx.end()) - vx.begin());
	for (int i = 1; i <= n; i++) {
		asd[i] = lower_bound(vx.begin(), vx.end(), ar[i].fr) - vx.begin() + 1;
	}
	for (int i = 1; i <= n; i++) {
		root[i] = ++siz;
		upd(root[i - 1], root[i], asd[i], ar[i].fr);
	}
	make(1, n, 1, 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);
	}
	ans = -1e18;
	if (m == 3) {
		for (int i = 2; i < n; i++) {
			ans = max(ans, pref[i - 1] + suf[i + 1] + ar[i].fr);
		}
	} else {
		solve();
	}
	cout << ans;
}

Compilation message (stderr)

cake3.cpp: In function 'long long int getsum(int, int, int, int, int)':
cake3.cpp:71:5: warning: unused variable 'res' [-Wunused-variable]
  ll res = 0;
     ^~~
cake3.cpp: At global scope:
cake3.cpp:120:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
cake3.cpp: In function 'int main()':
cake3.cpp:121: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:123: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: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76