| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 412912 | vlamarca | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fr(i,n) for(int i = 0; i<n; i++)
#define sz(v) (int)(v.size())
#define prin(a) cout << #a << " = " << a << endl
#define all(v) (v).begin(),(v).end()
typedef long long ll;
#define fi first
#define se second
struct Line{
// y = m*x + k
ll m,k,qnt;
ll eval(ll x){
return m*x+k;
}
Line(){}
Line(ll _m, ll _k, ll _qnt){
m = _m, k = _k, qnt = _qnt;
}
};
struct ChtDeque{
vector<Line> dq;
int l, r; // [l,r)
ChtDeque(){}
ChtDeque(int n){
dq.resize(n);
l = r = 0;
}
ll div(ll a, ll b){
return a/b - ( (a^b)<0 and a%b);
}
bool tirar(Line &l1, Line &l2, Line &l3){
if(l1.m==l2.m){
return l1.k>=l2.k;
}
return div(l2.k-l3.k,l3.m-l2.m)<=div(l1.k-l2.k,l2.m-l1.m);
}
void add(ll m, ll k, ll qnt){
m*=-1,k*=-1;
Line line(m,k,qnt);
while(r-l>=2){
if(tirar(dq[r-2],dq[r-1],line)) r--;
else break;
}
dq[r++] = line;
}
pair<ll,ll> query(ll x){
assert(r>l);
while(r-l>=2){
ll val_l = dq[l].eval(x);
ll val_l1 = dq[l+1].eval(x);
if(val_l1>=val_l) l++;
else break;
}
return {-dq[l].eval(x),dq[l].qnt};
}
};
vector<pair<ll,ll>> vp;
pair<ll,ll> f(ll c){
ChtDeque cht(sz(vp)+1);
ll udp = 0, uqnt = 0;
fr(i,sz(vp)){
ll ri,ci; tie(ri,ci) = vp[i];
ci++;
ll sub = 0;
if(i){
ll rj,cj; tie(rj,cj) = vp[i-1];
cj++;
if(cj>ri) sub = (cj-ri)*(cj-ri);
}
cht.add(-2*ri,ri*ri+udp+c-sub,uqnt);
ll dp, qnt; tie(dp,qnt) = cht.query(ci);
dp+=ci*ci;
qnt++;
udp = dp, uqnt = qnt;
}
return {udp,uqnt};
}
ll take_photos(int n, int m, int k, vector<int> vr, vector<int> vc){
vp.clear();
fr(i,n){
if(vc[i]<vr[i]) swap(vc[i],vr[i]);
vp.emplace_back(vr[i],vc[i]);
}
{
sort(all(vp));
reverse(all(vp));
vector<pair<ll,ll>> aux;
for(auto &[i,j] : vp){
if(!aux.empty() and aux.back().fi==i) continue;
while(!aux.empty() and j>=aux.back().se) aux.pop_back();
aux.emplace_back(i,j);
}
reverse(all(aux));
vp = aux;
}
k = min<ll>(k,sz(vp));
ll lo = 0, hi = (ll)m*m;
while(lo<hi){
ll mid = (lo+hi+1)/2;
if(f(mid).se>=k) lo = mid;
else hi = mid-1;
};
auto par = f(lo);
/*
prin(lo);
prin(k);
prin(par.fi);
prin(par.se);
for(int d = -2; d<=2; d++){
prin(lo+d);
prin(f(lo+d).fi);
prin(f(lo+d).se);
cout << endl;
}*/
return par.fi-(ll)k*lo+(par.se-k);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
ll ans;
/*
int n, m, k; cin >> n >> m >> k;
vector<int> vr(n), vc(n);
fr(i,n) cin >> vr[i] >> vc[i];
ans = take_photos(n,m,k,vr,vc);
cout << ans << endl;
//*/
///*
ans = take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}); //ans = 25
prin(ans);
ans = take_photos(2, 6, 2, {1, 4}, {4, 1}); //ans = 16
prin(ans);
ans = take_photos(3,11,2, {1,7,10}, {1,7,10}); //ans = 17
prin(ans);
ans = take_photos(4,4,4, {1,0,2,2}, {3,1,1,2}); //ans = 12
prin(ans);
//*/
}