| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 412453 | 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 prinv(v) cout << #v << " = "; for(auto it : v) cout << it << ", "; cout << endl
#define all(v) (v).begin(),(v).end()
typedef long long ll;
#define rmin(a,b) a = min<ll>(a,b)
#define rmax(a,b) a = max<ll>(a,b)
#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;
}
};
//querys em ordem de x decrescente
//insercoes de linhas com m (slopes) em ordem decrescente
struct ChtDeque{
vector<Line> dq;
int l, r; // [l,r)
ChtDeque(){}
ChtDeque(int n){ //n eh o maximo de linhas a serem inseridas
n+=5;
dq.resize(n+5);
l = r = 3;
}
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;
}
if(l<r and dq[l].m==m){
if(k>dq[l].k) dq[l] = line;
return;
}
dq[r++] = line;
}
pair<ll,ll> query(ll x){
assert(r>l);
while(r-l>=2){
if(dq[l+1].eval(x)>=dq[l].eval(x)) l++;
else break;
}
return {-dq[l].eval(x),dq[l].qnt};
}
};
vector<pair<ll,ll>> vp;
int debug = 0;
//ans min, k used
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++;
cht.add(-2*ri,ri*ri+udp+c,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;
}
/*
for(auto &[i,j] : vp){
prin(i);
prin(j);
cout << endl;
}
//*/
ll lo = 0, hi = m*m;
while(lo<hi){
ll mid = (lo+hi)/2;
if(f(mid).se<=k) hi = mid;
else lo = mid+1;
};
//prin(lo);
auto par = f(lo);
//prin(par.fi);
//prin(k);
//prin(par.se);
return par.fi-par.se*lo;
/*
lo = 30;
prin(lo);
auto par = f(lo);
prin(par.fi);
prin(k);
prin(par.se);
return par.fi-par.se*lo;
*/
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
ll ans = take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}); //ans = 25
//ll ans = take_photos(2, 6, 2, {1, 4}, {4, 1}); //ans = 16
//ll ans = take_photos(3, 11, 3, {1, 7,10}, {1, 7,10});
prin(ans);
}