| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 730078 | nguyentunglam | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define int long long
using namespace std;
const int N = 1e5 + 10;
pair<int, int> a[N];
long long l[N], r[N], f[N], g[N];
struct line {
long long m, c;
int idx;
long long eval(long long x) { return m * x + c; }
long long cut(line l) {
return (c - l.c) / (l.m - m);
}
};
struct CHT {
line s[N];
int st = 1, ed = 0;
void add(line cur) {
// cout << st << " " << ed << endl;
while (ed - st + 1 >= 2 && cur.cut(s[ed]) <= s[ed].cut(s[ed - 1])) --ed;
s[++ed] = cur;
}
line get(long long x) {
while (ed - st + 1 >= 2 && s[st].eval(x) >= s[st + 1].eval(x)) st++;
return s[st];
}
};
long long take_photos(int n, int m, int k, std::vector<int> RR, std::vector<int> CC) {
for(int i = 0; i < n; i++) {
a[i] = make_pair(RR[i], CC[i]);
if (a[i].fi > a[i].se) swap(a[i].fi, a[i].se);
}
sort(a, a + n, [] (const ii &A, const ii &B) {
if (A.fi != B.fi) return A.fi < B.fi;
return A.se > B.se;
});
int n2 = 0, mx = -1;
for(int i = 0; i < n; i++) if (a[i].se > mx) {
mx = a[i].se;
++n2;
l[n2] = a[i].fi;
r[n2] = a[i].se;
}
n = n2;
// for(int i = 1; i <= n; i++) cout << l[i] << " " << r[i] << endl;
r[0] = -1;
long long L = 0, R = 1e18, res = 1e18;
while (L <= R) {
long long mid = L + R >> 1;
CHT cht;
for(int i = 1; i <= n; i++) {
long long cost = (l[i] <= r[i - 1]) ? (r[i - 1] - l[i] + 1) * (r[i - 1] - l[i] + 1) : 0;
line cur = {-2LL * l[i], f[i - 1] - cost + l[i] * l[i], i - 1};
cht.add(cur);
line opt = cht.get(r[i] + 1);
g[i] = g[opt.idx] + 1;
f[i] = opt.eval(r[i] + 1) + (r[i] + 1) * (r[i] + 1) + mid;
}
// cout << mid << " " << g[n] << endl;
if (g[n] <= k) {
res = min(res, f[n] - mid * g[n]);
R = mid - 1;
}
else L = mid + 1;
}
return res;
}
#ifdef ngu
main() {
cout << take_photos(1, 7, 4, {0}, {0});
// cout << take_photos(5, 7, 3, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6});
// cout << take_photos(2, 6, 2, {1, 4}, {4, 1});
}
#endif // ngu