| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 930571 | guagua0407 | 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.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
const int mxn=1e5+5;
const ll inf=1e18;
vector<ll> dp(mxn);
vector<int> cnt(mxn);
vector<ll> g(mxn);
vector<int> x,y;
struct line{
ll a,b;
ll val(ll x){
return a*x+b;
}
};
vector<line> L(mxn);
ll check(line l1,line l2,line l3){
return (__int128)(l3.b-l1.b)*(l1.a-l2.a)<=(__int128)(l2.b-l1.b)*(l1.a-l3.a);
}
// y[r]^2+x[l+1]^2+1+2y[r]-2x[l+1]-2x[l+1]y[r]
// y[i]^2+2y[r]+1+min(-2y[r]x[l+1]+x[l+1]^2-2x[l+1]+dp[l]-g[l+1])
int check(int n,ll cost){
L[0]={-2*x[1],1ll*x[1]*x[1]-2*x[1]+cost};
deque<int> vec;
vec.push_back(0);
for(int i=1;i<=n;i++){
while((int)vec.size()>=2 and L[vec[0]].val(y[i])>=L[vec[1]].val(y[i])){
vec.pop_front();
}
dp[i]=1ll*y[i]*y[i]+2*y[i]+1+L[vec[0]].val(y[i]);
cnt[i]=cnt[vec[0]]+1;
L[i]={-2*x[i+1],1ll*x[i+1]*x[i+1]-2*x[i+1]+dp[i]-g[i+1]+cost};
while((int)vec.size()>=2 and check(L[vec[vec.size()-2]],L[vec.back()],L[i])){
vec.pop_back();
}
vec.push_back(i);
}
return cnt[n];
}
ll solve(int n,int m,int k){
k=min(k,n);
for(int i=1;i<=n;i++){
g[i]=(i==1?0:max(0,y[i-1]-x[i]+1));
g[i]*=g[i];
}
ll l=0,r=(ll)1e12+1;
while(l<r){
ll mid=(l+r)/2;
if(check(n,mid)<=k){
r=mid;
}
else{
l=mid+1;
}
}
//cout<<l<<'\n';
check(n,l);
return dp[n]-k*l;
}
ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c){
vector<pair<int,int>> vec(n);
for(int i=0;i<n;i++){
if(r[i]>c[i]) swap(r[i],c[i]);
vec[i]={c[i],r[i]};
}
sort(all(vec));
vector<pair<int,int>> st;
for(int i=0;i<n;i++){
while(!st.empty() and st.back().s>=vec[i].s){
st.pop_back();
}
st.push_back(vec[i]);
}
x.push_back(-1);
y.push_back(-1);
for(auto v:st){
x.push_back(v.s);
y.push_back(v.f);
}
return solve(st.size(),m,k);
}
/*signed main(){
int n,m,k;
cin>>n>>m>>k;
vector<int> r(n),c(n);
for(int i=0;i<n;i++){
cin>>r[i];
cin>>c[i];
}
cout<<take_photos(n,m,k,r,c)<<'\n';
}*/
//maybe its multiset not set
//yeeorz
//laborz