| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 748557 | AnhPham | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...)42
#endif
#define int long long
#define SZ(_v) (int)(_v).size()
#define all(_v) (_v).begin(), (_v).end()
#define pb push_back
#define FOR(_v, _l, _r) for (int _v = _l; _v <= _r; ++_v)
#define FOD(_v, _r, _l) for (int _v = _r; _v >= _l; --_v)
#define REP(_v, _r) for (int _v = 0; _v < _r; ++_v)
#define RED(_v, _r) for (int _v = _r - 1; _v >= 0; --_v)
const int N = (int)1e6 + 1, M = (int)1e3 + 1;
const int MOD = (int)1e9 + 7;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
#define f first
#define s second
void solve();
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
solve();
}
int n, m, k;
ii a[N], dp[N];
pii l[N];
int s, e, cnt;
int sq(int x) {
return x * x;
}
bool cp(pii x, pii y, pii z) {
return (x.s.f - z.s.f) * (y.s.s - x.s.s) >= (x.s.f - y.s.f) * (z.s.s - x.s.s);
}
int f(int x, int y) {
return l[x].s.f * y + l[x].s.s;
}
void update(int x, int y, int z) {
while (e - s > 1 && cp(l[e - 2], l[e - 1], { z, { x, y } }))
--e;
l[e++] = { z, { x, y } };
}
ii calc(int x) {
s = e = 0;
update(-2 * (a[0].f - 1), sq(a[0].f - 1), 0);
FOR(i, 1, cnt) {
while (e - s > 1 && f(s, a[i - 1].s) >= f(s + 1, a[i - 1].s))
++s;
dp[i] = { f(s, a[i - 1].s) + sq(a[i - 1].s) + x, dp[l[s].f].s + 1 };
update(-2 * (a[i].f - 1), dp[i].f + sq(a[i].f - 1) - sq(max(0ll, a[i - 1].s - a[i].f + 1)), i);
}
return dp[cnt];
}
int take_photos(vector<int> x, vector<int> y) {
REP(i, n)
a[i] = { min(x[i], y[i]), max(x[i], y[i]) };
sort(a, a + n, [&](ii x, ii y) {
return x.f == y.f ? x.s > y.s : x.f < y.f;
});
cnt = 1;
FOR(i, 1, n - 1)
if(a[i].s > a[cnt - 1].s)
a[cnt++] = a[i];
int l = 0, r = sq(m);
while(r - l > 1) {
int mid = (l + r) / 2;
k <= calc(mid).s ? l = mid : r = mid;
}
return calc(l).f - k * l;
}
void solve() {
cin >> n >> m >> k;
vector<int> x(n), y(n);
REP(i, n)
cin >> x[i] >> y[i];
cout << take_photos(x, y);
}