| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 935226 | Cyber_Wolf | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Problem: P6 - Aliens
// Contest: DMOJ - IOI '16
// URL: https://dmoj.ca/problem/ioi16p6
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const lg N = 1e5+5;
lg n, k;
lg dp[N];
lg opt[N];
vector<array<lg, 2>> p;
vector<lg> o;
void solve(lg lambda)
{
for(int i = 0; i <= n; i++) dp[i] = 2e18, opt[i] = 2e18;
dp[0] = opt[0] = 0;
deque<lg> slope, inter;
deque<lg> opts;
lg sz = 1;
opts.push_back(0);
slope.push_back(-2*p[0][1]);
inter.push_back(p[0][1]*p[0][1]-o[0]+dp[0]);
for(int i = 1; i <= n; i++)
{
while(sz > 1 && p[i-1][0]*slope[1]+inter[1] <= p[i-1][0]*slope[0]+inter[0])
{
opts.pop_front();
slope.pop_front();
inter.pop_front();
sz--;
}
dp[i] = p[i-1][0]*slope.front()+inter.front()+p[i-1][0]*p[i-1][0]+lambda;
opt[i] = opt[opts.front()]+1;
if(i < n)
{
lg x = -2*p[i][1], y = p[i][1]*p[i][1]-o[i]+dp[i];
while(sz > 1 && (inter[sz-2]-y)*(slope[sz-1]-slope[sz-2]) <= (inter[sz-2]-inter[sz-1])*(x-slope[sz-2]))
{
slope.pop_back();
inter.pop_back();
opts.pop_back();
sz--;
}
slope.push_back(x);
inter.push_back(y);
opts.push_back(opt[i]);
sz++;
}
}
return;
}
lg take_photos(int NM, int m, int K, int r[], int c[])
{
n = NM, k = K;
set<array<lg, 2>> pt;
for(int i = 0; i < n; i++)
{
if(r[i] < c[i]) swap(r[i], c[i]);
pt.insert({r[i], -c[i]});
}
for(auto [x, y] : pt)
{
while(p.size() && p.back()[1] >= -y) p.pop_back();
p.push_back({x, -y});
}
for(auto &it : p) it[1]--;
lg la = -1e18;
for(auto it : p)
{
if(la-it[1] > 0) o.push_back((la-it[1])*(la-it[1]));
else o.push_back(0);
la = it[0];
}
n = p.size();
lg s = -1, e = 1e15;
k = min(k, n);
while(e-s > 1)
{
lg mid = (s+e)/2;
solve(mid);
// cout << mid << '\n';
// cout << dp[n] << ' ' << opt[n] << '\n';
if(opt[n] >= k)
{
s = mid;
}
else{
e = mid;
}
}
solve(s);
return dp[n]-k*s;
}
int main()
{
int n, m, k;
cin >> n >> m >> k;
int r[n], c[n];
for(int i = 0; i < n; i++)
{
cin >> r[i] >> c[i];
}
cout << take_photos(n, m, k, r, c) << '\n';
return 0;
}
/*
m1x+c1 <= m2x+c2
m1x-m2x <= c2-c1
x <= (c2-c1)/(m1-m2)
5 7 2
0 3
4 4
4 6
4 5
4 6
*/