| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 594513 | rsjw | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct points {
int x, y;
bool operator<(const points &ri) const & {
if (x == ri.x)
return y > ri.y;
return x < ri.x;
}
bool operator==(const points &ri) const & { return y == ri.y && x == ri.x; }
} a[100010];
int num, ans;
int P[100010];
int Q[100010];
int f[100010], g[100010];
int Y(int x) { return f[x] + Q[x] * Q[x] - P[x]; }
int X(int x) { return 2 * Q[x]; }
double Slope(int x, int y) { return (Y(y) - Y(x)) / (X(y) - X(x)); }
int n;
int q[100010];
void fee(int extra) { //拍照次数 g 最大值
f[0] = g[0] = 0;
int i, h = 1, t = 1;
q[t++] = 0;
for (i = 1; i <= n; ++i) {
while (t - h > 1 && Slope(q[h], q[h + 1]) < a[i].y)
h++;
f[i] = Y(q[h]) - X(q[h]) * a[i].y - extra + a[i].y * a[i].y,
g[i] = f[q[h]] + 1;
while (t - h > 1 && Slope(q[t - 1], q[t - 2]) >= Slope(q[t - 1], i))
t--;
q[t++] = i;
}
num = g[n];
ans = f[n];
}
signed main() {
//freopen("1.in", "r", stdin);
int m, k, i;
cin >> n >> m >> k;
for (i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y, a[i].x++, a[i].y++,
a[i].x > a[i].y && (swap(a[i].x, a[i].y), 0);
sort(a + 1, a + n + 1);
int maxn = 0;
for (i = 1; i <= n; i++) {
if (a[i].y > maxn)
maxn = a[i].y;
else
a[i] = a[i - 1];
}
n = unique(a + 1, a + n + 1) - a - 1;
for (i = 0; i < n; i++) {
P[i] = max(a[i].y - a[i + 1].x + 1, 0ll);
P[i] *= P[i];
Q[i] = a[i + 1].x - 1;
}
int l = -1e12, r = 0;
int c;
int Ans = -1;
while (l <= r) {
c = (l + r) / 2;
fee(c);
if (num <= k) {
l = c + 1;
} else {
Ans = k * c + ans;
r = c - 1;
}
}
if (Ans == -1)
fee(0), Ans = ans;
cout << Ans << endl;
return 0;
}