| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 597643 | cheissmart | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7;
const ll oo = 1e18;
struct DS {
struct line {
ll m, b;
int id;
line(ll _m, ll _b, int _id) { m = _m, b = _b, id = _id; }
ll operator () (ll x) { return m * x + b; }
ll when(line l) { // when will l beat *this
assert(l.m < m);
ll he = l.b - b, be = m - l.m;
if(he % be == 0) return he / be + 1;
else if (he < 0) return he / be;
else return he / be + 1;
}
};
deque<line> dk;
void insert(ll m, ll b, int id) { // m strictly decreasing
line l(m, b, id);
while(SZ(dk) >= 2 && dk[SZ(dk) - 2].when(dk.back()) >= dk.back().when(l)) l.pop_back();
dk.PB(l);
}
int qry(ll x) {
while(SZ(dk) >= 2 && dk[0](x) > dk[1](x))
dk.pop_front();
return dk[0].id;
}
};
long long take_photos(int n, int C, int k, vi r, vi c) {
V<pi> a;
for(int i = 0; i < n; i++) {
int x = r[i] + c[i], y = abs(r[i] - c[i]);
a.EB(x, y);
}
sort(ALL(a));
auto cover = [&] (pi x, pi y) {
return abs(x.F - y.F) <= x.S - y.S;
};
V<pi> stk;
for(pi p:a) {
if(SZ(stk) && cover(stk.back(), p))
continue;
while(SZ(stk) && cover(p, stk.back()))
stk.pop_back();
stk.PB(p);
}
a = stk;
n = SZ(a);
auto intersect = [&] (int i) -> ll {
if(i == 0) return 0;
if(a[i].F - a[i - 1].F > a[i - 1].S + a[i].S) return 0;
int d = (a[i - 1].S - a[i].S + a[i].F - a[i - 1].F) / 2;
return 1LL * (a[i - 1].S - d + 1) * (a[i - 1].S - d + 1);
};
auto go = [&] (ll x) -> pair<ll, int> {
V<ll> dp(n + 1);
vi take(n + 1);
auto get_f = [&] (int j) -> pair<ll, ll> {
int bj = (a[j].F + a[j].S) / 2;
int cj = (a[j].S - a[j].F) / 2 + 1;
ll mj = 2LL * cj;
ll kj = dp[j] - intersect(j) + x + 1LL * cj * cj;
return {mj, kj};
};
DS ds;
for(int i = 1; i <= n; i++) {
{
auto[m, b] = get_f(i - 1);
ds.insert(m, b, i - 1);
}
int bi = (a[i - 1].F + a[i - 1].S) / 2;
dp[i] = oo;
int j = ds.qry(bi);
auto[m, b] = get_f(j);
dp[i] = m * bi + b + 1LL * bi * bi;
take[i] = take[j] + 1;
}
return {dp[n], take[n]};
};
{
auto[val, take] = go(0);
if(take <= k) return val;
}
ll lb = 0, rb = ll(1e12) + 1;
while(lb <= rb) {
ll mb = (lb + rb) / 2;
auto[val, take] = go(mb);
if(take <= k) {
rb = mb - 1;
} else {
lb = mb + 1;
}
}
auto[val, take] = go(lb);
return val - lb * k;
}