Submission #157011

#	Time	Username	Problem	Language	Result	Execution time	Memory
157011		DrumpfTheGodEmperor	Cake 3 (JOI19_cake3)	C++14	0 / 100	2 ms	376 KiB

cake3

#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const double EPS = 1e-6;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 2e5 + 5;
int n, k, ans[N];
struct Cake {
	int v, c;
	bool operator<(const Cake &rhs) const { return c < rhs.c; }
} c[N];
double ansOut = 0;
double v2[N], sumV[N], cnt[N];
int solve(double penalty) {
	fw (i, 0, n) v2[i] = c[i].v, v2[i] -= penalty;
	fw (i, 0, n) {
		sumV[i] = (i ? sumV[i - 1] : 0);
		cnt[i] = (i ? cnt[i - 1] : 0);
		if (v2[i] > 0) {
			sumV[i] += v2[i];
			cnt[i]++;
		}
	}
	int mxL = -1, ansL, ansR;
	double mx = -infll, ans = -infll;
	fw (i, 0, n) {
		//l and r must be at least 3 elements apart.
		double val = (i ? sumV[i - 1] : 0) + v2[i] - 2 * c[i].c;
		if (val + mx > ans) {
			ans = val + mx;
			ansL = mxL;
			ansR = i;
		}
		
		
		if (v2[i] - sumV[i] + 2 * c[i].c > mx) {
			mx = v2[i] - sumV[i] + 2 * c[i].c;
			mxL = i;
		}
	}
	ansOut = ans;
	return (ansR ? cnt[ansR - 1] : 0) - cnt[ansL] + 2;
}
double bs(double l, double r) {
	if (l + EPS > r) return l;
	double m = (l + r) / 2;
	int lol = solve(m);
	if (lol > k) return bs(m, r); //Increase penalty to pick less elements
	return bs(l, m);
}
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	fw (i, 0, n) cin >> c[i].v >> c[i].c;
	sort(c, c + n);	//Minimum sum of depth differences is 2 * (max - min)
	//Use Alien's trick: Add a penalty for each piece taken until the number of pieces is exactly K.
	double optPenalty = bs(-2e9, 2e9);
	solve(optPenalty);
	cout << (long long)(ansOut + optPenalty * k);
	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'long long int solve(double)':
cake3.cpp:54:26: warning: 'ansR' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return (ansR ? cnt[ansR - 1] : 0) - cnt[ansL] + 2;
                     ~~~~~^~~
cake3.cpp:54:46: warning: 'ansL' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return (ansR ? cnt[ansR - 1] : 0) - cnt[ansL] + 2;
                                      ~~~~~~~~^

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