제출 #927821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927821		12345678	Aliens (IOI16_aliens)	C++17	100 / 100	144 ms	11248 KiB

aliens

#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;
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40