Submission #930856

#	Time	Username	Problem	Language	Result	Execution time	Memory
930856		Khanhcsp2	Aliens (IOI16_aliens)	C++17	100 / 100	178 ms	10216 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
const int N = 1e5+5;
ll dp[N],l[N],r[N],c[N],m[N];
int cnt[N],n;

struct line
{
    ll m = 0,c = 0;
    int cnt = 0;
    line() {}
    line(ll _m,ll _c,int _cnt):m(_m),c(_c),cnt(_cnt) {}
    ll eval(ll x)
    {
        return m*x+c;
    }
};
deque<line>hull;
void add(line t)
{
    while(sz(hull)>1)
    {
        line a = hull[sz(hull)-2];
        line b = hull[sz(hull)-1];
        if((t.c - a.c) * (b.m - t.m) >= (a.m - t.m) * (t.c - b.c))hull.pop_back();
        else break;
    }
    hull.push_back(t);
}

int num = 0;
ll query(ll x)
{
    while(sz(hull)>1 && hull[1].eval(x) >= hull[0].eval(x))hull.pop_front();
    num = hull[0].cnt;
    return hull[0].eval(x);
}
int find(ll mid)
{
    dp[0] = cnt[0] = 0;
    hull.clear();
    add(line(m[0],c[0],0));
    for(int i=1; i<=n; i++)
    {
        dp[i] = r[i] * r[i]  - query(r[i]) + mid;
        cnt[i] = num+1;
        if(i!=n)add(line(m[i],c[i] - dp[i],cnt[i]));
    }
    return cnt[n];
}
ll take_photos(int N, int M, int K, vector<int> RR, vector<int> C)
{
    n = N;
    vector<pii>tmp,p;
    for(int i=0; i<n; i++)tmp.pb({min(RR[i],C[i]),max(RR[i],C[i])});
    sort(all(tmp),[&](pii x,pii y)
    {
        if(x.fi==y.fi)return x.se > y.se;
        return y.fi > x.fi;
    });
    int mx = -1;
    for(pii x:tmp)
    {
        if(mx >= x.se)continue;
        mx = max(mx,x.se);
        p.pb(x);
    }
    n = sz(p);
    p.pb({-1,-1});
    sort(all(p),[&](pii x,pii y)
    {
        return y.se > x.se;
    });
    for(int i=0; i<=n; i++)
    {
        l[i] = p[i].fi;
        r[i] = p[i].se;
    }
    for(int i=0; i<n; i++)
    {
        m[i] = 2*l[i+1] - 2;
        c[i] = max(r[i] - l[i+1] + 1,0LL);
        c[i]*=-c[i];
        c[i] += (l[i+1]-1)*(l[i+1]-1);
        c[i]*=-1;
    }
    ll L = 0,R = 1e15;
    K = min(K,n);
    while(R>L)
    {
        ll mid = (L+R+1)/2;
        if(find(mid) >= K)L = mid;
        else R = mid-1;
    }
    find(L);
    ll ans = dp[n] - K*1LL * L;
    return ans;
}

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