| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 546544 | CPSC | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
# include "aliens.h"
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ld long double
#define int long long
#define pii pair <long long, long long>
using namespace std;
const int N = 1e6 + 5;
long long n,m,k,sk,mx,r[N],c[N],mn,raod,b;
long long ans;
pii dp[N];
struct pi {
long long l, r;
};
pi a[N];
struct line {
int k,b,raod;
};
deque <line> dq;
bool cmp(pi a, pi b) {
if (a.l != b.l) return (a.l < b.l);
else
return (b.r > a.r);
}
long long go(long long le, long long ri) {
if (le > ri) return 0;
return (ri - le + 1LL)*(ri - le + 1LL);
}
ld X(line a, line b) {
if (a.k - b.k == 0) assert(false);
return (ld)((ld)(b.b - a.b)/(ld)(a.k - b.k));
}
int getans(int x) {
while (dq.size() >= 2) {
line cur = dq[0];
line prev = dq[1];
if (X(cur,prev) < x)
dq.pop_front();
else break;
}
raod = dq.front().raod + 1;
sk = dq.front().k;
b = dq.front().b;
return sk*x + b;
}
void add(int k, int b, int raod) {
//cout<<k<<" "<<b<<" "<<raod<<endl;
if(!dq.size()) {
dq.push_back({k,b,raod}); return ;
}
if (dq.back().k == k) {
if (dq.back().b > b) dq.pop_back();
else {
if (dq.back().raod <= raod) return;
else dq.pop_back();
}
}
line toadd = {k,b,raod};
while (dq.size() >= 2) {
line cur = dq.back();
line prev = dq[dq.size() - 2];
if (X(cur,prev) > X(prev,toadd)) {
dq.pop_back();
}
else break;
}
dq.push_back(toadd);
}
long long check(long long mid) {
while (dq.size()) dq.pop_back();
dp[0] = {0,0};
int sk,b;
raod = 0;
sk = -2*(a[1].l - 1);
b = 0 + (a[1].l - 1)*(a[1].l - 1) - max(0LL, go(a[1].l, a[0].r));
//cout<<b<<endl;
add(sk,b,raod);
//add(-2*a[1].l, 0 + a[1].l*a[1].l - max(0, go(a[1].l, a[0].r)),0);
for (long long i = 1; i <= n; i++) {
dp[i] = {1e15,1e15};
//cout<<"idx -- >"<<i<<" ";
dp[i].f = getans(a[i].r) + a[i].r*a[i].r + mid;
dp[i].s = raod;
//cout<<i<<" "<<dp[i].f<<" "<<dp[i].s<<endl;
// if (i == 3) cout<<-2*(a[i + 1].l - 1)<<" "<<dp[i].f - max(0LL,go(a[i + 1].l,a[i].r)) + (a[i + 1].l - 1) * (a[i + 1].l - 1)<<endl;
if (i != n)
add(-2*(a[i + 1].l - 1), dp[i].f - max(0LL,go(a[i + 1].l,a[i].r)) + (a[i + 1].l - 1) * (a[i + 1].l - 1), raod);
}
//cout<<dp[n].s<<" "<<k<<endl;
return (dp[n].s <= k);
}
long long take_photos(int nn, int mmm, int kk, vector < int > r, vector < int > c) {
n = nn;
m = mmm;
k = kk;
for (int i = 0; i < n; i++) {
r[i]++; c[i]++;
mn = min(r[i], c[i]); mx = max(r[i],c[i]);
a[i + 1].l = mn; a[i + 1].r = mx;
}
sort(a + 1, a + n + 1, cmp);
long long mm = 0;
mx = 0;
for (int i = 1; i <= n; i++) {
if (mx >= a[i].r) { }
else {
mm++; a[mm].l = a[i].l; a[mm].r = a[i].r;
}
mx = max(mx,(long long)a[i].r);
}
long long le, ri,ans1 = 1e15,ans;
n = mm;
le = 0;
ri = m*m;
while (le <= ri) {
long long mid = (le + ri) / 2;
if (check(mid)) {
//cout<<mid<<endl;
ans1 = dp[n].f - k * mid;
ans = mid; ri = mid - 1;
} else { le = mid + 1; }
}
//cout<<ans<<endl;
return ans1;
}
/*
main() {
int n, m, k;
assert(3 == scanf("%d %d %d", &n, &m, &k));
std::vector<int> r(n), c(n);
for (int i = 0; i < n; i++) {
assert(2 == scanf("%d %d", &r[i], &c[i]));
}
long long ans = take_photos(n, m, k, r, c);
printf("%lld\n", ans);
return 0;
}*/