| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1221976 | Szymon_Pilipczuk | Aliens (IOI16_aliens) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e12;
vector<pair<int,int>> t;
vector<pair<ll,ll>> co;
int cn;
ll sq(ll a)
{
return a*a;
}
vector<vector<ll>> tr;
void add(int p,ll a,ll b,int k)
{
ll c = tr[p][0], d = tr[p][1], e = tr[p][2],l = tr[p][3],r = tr[p][4];
if(c*(l+r)/2 + d > a*(l+r)/2 + b)
{
tr[p][0] = a;
tr[p][1] = b;
tr[p][2] = k;
a = c;
b = d;
k = e;
c = tr[p][0];
d = tr[p][1];
e = tr[p][2];
}
if(c*l + d > a*l + b)
{
if(tr[p][5] != -1)
{
add(tr[p][5],a,b,k);
}
else if(l <= (l+r)/2-1)
{
tr[p][5] = tr.size();
tr.pb({a,b,k,l,(l+r)/2-1,-1,-1});
}
}
else
{
if(tr[p][6] != -1)
{
add(tr[p][6],a,b,k);
}
else if((l+r)/2+1<=r)
{
tr[p][6] = tr.size();
tr.pb({a,b,k,(l+r)/2+1,r,-1,-1});
}
}
}
pair<ll,ll> check(int p,ll c)
{
ll l = tr[p][3],r = tr[p][4];
pair<ll,ll> ans = {tr[p][0]*c+tr[p][1],tr[p][2]};
//cerr<<tr[p][0]<<" "<<tr[p][1]<<" "<<tr[p][2]<<" "<<p<<" "<<c<<" a\n";
if(c < (l+r)/2 && tr[p][5] != -1)
{
pair<ll,ll> cu = check(tr[p][5],c);
if(cu.st < ans.st)
{
ans = cu;
}
}
else if((l+r)/2 < c && tr[p][6] != -1)
{
pair<ll,ll> cu = check(tr[p][6],c);
if(cu.st < ans.st)
{
ans = cu;
}
}
return ans;
}
pair<ll,ll> solve(ll c)
{
tr.clear();
tr.pb({-2 * co[0].st,sq(co[0].st),0,0,infl,-1,-1});
vector<pair<ll,ll>> ans(cn);
rep(i,cn)
{
ans[i] = {check(0,co[i].nd+1).st + sq(co[i].nd+1) + c,check(0,co[i].nd+1).nd+1};
if(i != cn-1) add(0,-2 * co[i+1].st,ans[i].st + sq(co[i+1].st) - sq(max(co[i].nd -co[i+1].st+1,0LL)) ,ans[i].nd);
// cerr<<c<<" "<<co[i+1].st<<" "<<ans[i].st<<" "<<ans[i].nd<<" "<<i<<"\n";
}
return {ans[cn-1].st - ans[cn-1].nd*c,ans[cn-1].nd};
}
ll take_photos(int n,int m,int k,vector<int> r,vector<int> c)
{
rep(i,n)
{
if(r[i] > c[i])
{
swap(r[i],c[i]);
}
t.pb({r[i],c[i]});
}
sort(all(t));
int mxc = -1;
rep(i,n)
{
if(i != n-1 && t[i].st == t[i+1].st)
{
continue;
}
if(t[i].nd > mxc)
{
co.pb(t[i]);
mxc = t[i].nd;
}
}
cn = co.size();
ll l = -1;
ll rr = infl;
pair<ll,ll> cl;
ll cc;
//cerr<<endl<<endl;
while(l + 1 < rr)
{
ll mid = (l+rr)/2;
pair<ll,ll> cu = solve(mid);
cl = cu;
cc = mid;
if(cu.nd < k)
{
rr = mid;
}
else if(cu.nd > k)
{
l = mid;
}
else
{
//cerr<<cu.st<<"\n";
return cu.st;
}
}
//<<cl.nd<<" "<<cc<<" "<<cl.st<<"\n";
return cl.st + cc * (cl.nd-k);
}
int main()
{
int n,m,k;
cin>>n>>m>>k;
vector<int> r,c;
rep(i,n)
{
int a,b;
cin>>a>>b;
r.pb(a);
c.pb(b);
}
cout<<take_photos(n,m,k,r,c)<<"\n";
}