Submission #655100

#TimeUsernameProblemLanguageResultExecution timeMemory
655100ziduoAliens (IOI16_aliens)C++17
100 / 100
217 ms6964 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pf printf #define pb push_back #define ppb pop_back #define ppf pop_front #define INF 1023456789 #define sz(x) ((int)x.size()) #define all(x) x.begin(),x.end() typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef pair<int,int> ii; typedef pair<pair<ll,ll>,int> line; #define maxn 100005 int n,cnt[maxn]; ll dp[maxn]; deque<line> dq; vector<ii> pts,tmp; inline ll sq(ll x){ return x*x; } inline ld poi(line a,line b){ auto[m1,c1]=a.fi; auto[m2,c2]=b.fi; return (ld)(c1-c2)/(m2-m1); } inline ll eval(line a,ll x){ return a.fi.fi*x+a.fi.se; } int calc(ll cost){ while(!dq.empty())dq.ppb(); for(int i=1;i<n;++i){ ll m=-2*(pts[i].fi-1);//always distinct ll c=dp[i-1]+cost+sq(pts[i].fi-1)-sq(max(0,pts[i-1].se-pts[i].fi+1)); line l={{m,c},i-1}; while(sz(dq)>=2&&poi(dq[sz(dq)-1],l)<=poi(dq[sz(dq)-1],dq[sz(dq)-2]))dq.ppb(); dq.pb(l); while(sz(dq)>=2&&eval(dq[0],pts[i].se)>eval(dq[1],pts[i].se))dq.ppf(); dp[i]=eval(dq[0],pts[i].se)+sq(pts[i].se); cnt[i]=cnt[dq[0].se]+1; } return cnt[n-1]; } ll take_photos(int _n,int m,int k,vi r,vi c){ n=_n; for(int i=0;i<n;++i){ if(r[i]>c[i])swap(r[i],c[i]); tmp.pb({r[i],c[i]}); } sort(all(tmp),[](ii &a,ii&b){ if(a.fi==b.fi)return a.se>b.se; else return a.fi<b.fi; }); pts.pb({-1,-1}); for(int i=0;i<n;++i){ if(pts.back().se<tmp[i].se)pts.pb(tmp[i]); } n=pts.size(); ll lo=0,hi=1e12,mid,res=1e12; while(lo<=hi){ mid=(lo+hi)>>1; if(calc(mid)<=k)res=mid,hi=mid-1; else lo=mid+1; } calc(res); return dp[n-1]-res*k; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...