| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1082653 | hqminhuwu | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
template<class X, class Y>
bool minz(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
} return false;
}
template<class X, class Y>
bool maxz(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
} return false;
}
const int N = 1e6 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;
struct line {
ll m, c;
ll eval (ll x) { return m * x + c; }
ld its (line l) { return (ld) (c - l.c) / (l.m - m); }
};
ll sqr (ll x){
return x * x;
}
ll dp[N], cnt[N];
vector <pll> v;
map <ll, ll> z;
void calc (ll x){
deque <line> dq;
deque <int> dqcnt;
dq.push_front({-2 * v[0].st, x + 1 + sqr(v[0].st) - 2 * v[0].st});
dqcnt.push_front(0);
forf (i, 0, v.size()){
while (dq.size() >= 2 && dq.back().eval(v[i].nd) > dq[dq.size() - 2].eval(v[i].nd)){
dq.pop_back();
dqcnt.pop_back();
}
dp[i] = dq.back().eval(v[i].nd) + sqr(v[i].nd) + 2 * v[i].nd;
cnt[i] = cnt[dqcnt.back()] + 1;
line cur = {-2 * v[i].st, dp[i] + x + 1 - sqr(max(0ll, v[i].nd - v[i + 1].st + 1))
+ sqr(v[i + 1].st) - 2 * v[i + 1].st};
while (dq.size() >= 2 && cur.its(dq[0]) >= dq[0].its(dq[1])){
dq.pop_front();
dqcnt.pop_front();
}
dqcnt.push_front(cnt);
dq.push_front(cur);
}
}
ll take_photos (int n, int m, int k, vector<int> r, vector<int> c){
forf (i, 0, n){
if (r[i] > c[i]) swap(r[i], c[i]);
maxz(z[r[i]], c[i]);
}
ll mx = 0;
for (pll t : z){
if (t.nd > mx){
v.pb(t);
mx = t.nd;
}
}
ll l = 0, h = 1ll * m * m;
n = v.size() - 1;
// for (pii t : v)
// cout << t.st << " " << t.nd << "\n";
while (l < h){
ll mid = (l + h) >> 1;
calc(mid);
//cout << mid << " " << cnt[n] << endl;
if (cnt[n] > k)
l = mid + 1;
else h = mid;
}
calc(l);
//cout << dp[n] << " " << cnt[n] << " " << l << endl;;
return dp[n] - k * l;
}