Submission #938025

#	Time	Username	Problem	Language	Result	Execution time	Memory
938025		DobromirAngelov	Aliens (IOI16_aliens)	C++14	100 / 100	214 ms	8900 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;

const int MAXN=1e5+5;
const long long INF=1e18;

struct Line
{
    long long k,n;
    long long st;
    int num;
    Line() {};
    Line(long long _k,long long _n,long long _st,int _num)
    {
        k=_k;
        n=_n;
        st=_st;
        num=_num;
    }
};

int n,m,k;
pair<int,int> tmp[MAXN];
vector<pair<long long,long long> > a;
long long dp[MAXN];
int seg[MAXN];
Line lines[MAXN];
int beg=0, en=-1;

long long crossX(Line a,Line b)
{
    long long diffK=a.k-b.k;
    long long diffN=b.n-a.n;
    if(diffK==0)
    {
        if(a.n>b.n) return INF;
        else return 0;
    }
    return (diffN+diffK-1)/diffK;
}

void addLine(Line cur)
{
    while(en-beg+1>0 && crossX(lines[en], cur)<=lines[en].st) en--;
    if(en-beg+1>0) cur.st=crossX(lines[en], cur);
    lines[++en]=cur;
}

pair<int,long long> query(long long x)
{
    while(en-beg+1>1 && lines[beg+1].st<=x) beg++;
    return {lines[beg].num, lines[beg].k*x+lines[beg].n};
}

void resetLines()
{
    beg=0;
    en=-1;
}

int solve(long long pen)
{
    resetLines();
    dp[0]=0;
    seg[0]=0;
    for(int i=1; i<=n; i++)
    {
        long long x=a[i].fi;
        long long t=max(0LL, a[i-1].se-x+1);
        addLine(Line(-(x-1)*2, (x-1)*(x-1)-t*t+dp[i-1]+pen, 0, i));
        pair<int,long long> qr=query(a[i].se);
        dp[i]=qr.se+a[i].se*a[i].se;
        seg[i]=seg[qr.fi-1]+1;
    }
    return seg[n];
}

long long take_photos(int _n, int _m, int _k, std::vector<int> _r, std::vector<int> _c)
{
    n=_n; m=_m; k=_k;
    for(int i=0; i<n; i++)
    {
        _r[i]++; _c[i]++;
        if(_r[i]>_c[i]) swap(_r[i], _c[i]);
        tmp[i+1].fi=_r[i], tmp[i+1].se=_c[i];
    }

    sort(tmp+1,tmp+n+1,[](pair<long long,long long> x,pair<long long,long long> y)
    {
        if(x.fi==y.fi) return x.se>y.se;
        return x.fi<y.fi;
    });
    a.push_back({0,0});
    for(int i=1; i<=n; i++)
    {
        if(tmp[i].fi>a.back().fi && tmp[i].se>a.back().se) a.push_back(tmp[i]);
    }
    n=a.size()-1;

    k=min(k,n);
    long long l=0,r=1e18;
    while(l<r)
    {
        long long mid=(l+r+1)/2;
        if(solve(mid)>=k) l=mid;
        else r=mid-1;
    }

    solve(l);
    long long ans=dp[n]-k*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