Submission #927821

#TimeUsernameProblemLanguageResultExecution timeMemory
92782112345678Aliens (IOI16_aliens)C++17
100 / 100
144 ms11248 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define ll long long const ll nx=1e5+5, inf=1e17; ll area[nx], L=0, R=1e12+5, df[nx]; stack<ll> s; pair<ll, ll> res; struct point { ll x, y; bool operator< (const point &o) const { if (x==o.x) return y>o.y; return x<o.x; } } v[nx], p[nx]; struct line { ll m, c, idx; double p; line(ll m, ll c, ll idx, ll p): m(m), c(c), idx(idx), p(p){} }; struct convexhull { deque<line> dq; void add(ll m, ll c, ll idx) { line nw=line(m, c, idx, inf); while (dq.size()>=2&&(double)(nw.c-dq[dq.size()-2].c)/(dq[dq.size()-2].m-nw.m)<=dq[dq.size()-2].p) dq.pop_back(); if (!dq.empty()) dq.back().p=((double)(nw.c-dq.back().c)/(dq.back().m-nw.m)); dq.push_back(nw); } pair<ll, ll> query(ll x) { while (x>dq.front().p) dq.pop_front(); return {dq.front().m*x+dq.front().c, dq.front().idx}; } } cvh; pair<ll, ll> solve(ll x, int sz) { vector<pair<ll, ll>> dp(nx); while (cvh.dq.size()>0) cvh.dq.pop_back(); for (int i=1; i<=sz; i++) { dp[i]={df[i]+x, -1}; if (i!=1) cvh.add(-2*p[i].y, p[i].y*p[i].y-2*p[i].y+1-area[i]+dp[i-1].first, i); if (!cvh.dq.empty()) { auto tmp=cvh.query(p[i].x); tmp.first=tmp.first+p[i].x*p[i].x+2*p[i].x+x; tmp.second=dp[tmp.second-1].second-1; dp[i]=min(dp[i], tmp); } } return dp[sz]; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { for (int i=0; i<n; i++) if (r[i]>c[i]) swap(r[i], c[i]); for (int i=1; i<=n; i++) v[i].x=c[i-1], v[i].y=r[i-1]; sort(v+1, v+n+1); for (int i=1; i<=n; i++) { while (!s.empty()&&v[s.top()].y>=v[i].y) s.pop(); s.push(i); } n=s.size(); while (!s.empty()) p[s.size()]=v[s.top()], s.pop(); for (int i=2; i<=n; i++) if (p[i-1].x>=p[i].y) area[i]=(p[i-1].x-p[i].y+1)*(p[i-1].x-p[i].y+1); for (int i=1; i<=n; i++) df[i]=(p[i].x-p[1].y+1)*(p[i].x-p[1].y+1); k=min(k, n); while (L<R) { ll md=(L+R)/2; res=solve(md, n); if (-res.second<=k) R=md; else L=md+1; } //cout<<"sz "<<n<<'\n'; //cout<<"here "<<L<<' '<<solve(L, n).first<<' '<<solve(L, n).second<<'\n'; return solve(L, n).first-k*L; }
#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...