Submission #166476

#	Time	Username	Problem	Language	Result	Execution time	Memory
166476		knon0501	Aliens (IOI16_aliens)	C++14	100 / 100	171 ms	9052 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> pp;
#define f first
#define s second
pp a[100005];
long long dp[100005];
pair<pp,int> ss[100005];
int nn;
pp aa[100005];
int p[100005];
inline long double cr(pp x,pp y){
    if(x.f==y.f)return 0;
    return (long double)(y.s-x.s)/(long double)(x.f-y.f);
}
pair<long long,long long> CHT(long long c){
    int i,j=1;
    int t=0;
    for(i=1 ; i<=nn ; i++){
        pair<pp,int> k={{-2*aa[i].f,aa[i].f*aa[i].f+dp[i-1]+c-(long long)(i>=2)*max((long long)0,aa[i-1].s-aa[i].f)*max((long long)0,aa[i-1].s-aa[i].f)},p[i-1]};
        while(t>=2 && cr(ss[t].f,ss[t-1].f)>=cr(ss[t].f,k.f))t--;
        ss[++t]=k;
        for( ; j<t && cr(ss[j].f,ss[j+1].f)<=(long double)aa[i].second ;j++);
        dp[i]=ss[j].f.f*aa[i].s+ss[j].f.s+aa[i].s*aa[i].s;
        p[i]=ss[j].s+1;
    }
    return {p[nn],dp[nn]};
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    int i,j=0;
    for(i=1 ; i<=n ; i++){
        a[i]={r[i-1],c[i-1]};
        if(a[i].s<a[i].f)swap(a[i].f,a[i].s);
    }
    sort(a+1,a+n+1);
    a[0].f=-1;
    a[0].s=-1;
    a[n+1].f=-1;
    for(i=1 ; i<=n ; i++){
        if(a[i].s<=a[j].s || a[i].f==a[i+1].f);
        else{
            aa[++nn]=a[i];
            j=i;
        }
    }
    for(i=1 ; i<=nn ; i++)aa[i].f--;

    long long ans=0;
    long long lef=0;
    long long rig=(long long)m*m;

    while(rig>=lef){
        long long mid=(lef+rig)/2;
        pp v=CHT(mid);
        ans=max(ans,-mid*k+v.s);
        if(v.f<=k)rig=mid-1;
        else lef=mid+1;
    }

    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