Submission #224867

#	Time	Username	Problem	Language	Result	Execution time	Memory
224867		urd05	Aliens (IOI16_aliens)	C++14	100 / 100	155 ms	8696 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<long long,long long> P;
P arr[100000];
P temp[100000];
long long dp[100005]; //dp[i][j] : minimum grid to fill if we should take a picture unitl i-th place with j pictures.
const long long INF=1e18;
long long n,m,k;
int sz=0;
int ind=0;
 
struct Line {
    long long a,b;
};
 
struct Fraction {
    long long up,down;
};
 
Fraction cross(Line one,Line two) {
    if (one.a<two.a) {
        swap(one,two);
    }
    return {two.b-one.b,one.a-two.a};
}
 
bool cmp(Fraction one,Fraction two) {
    __int128 ou=one.up;
    __int128 od=one.down;
    __int128 tu=two.up;
    __int128 td=two.down;
    return ou*td<tu*od;
}
 
Line line[100513];
 
void insert(Line l) {
    if (sz>=1&&line[sz-1].a==l.a) {
        if (l.b>line[sz-1].b) {
            line[sz-1]=l;
        }
        return;
    }
    while (sz>1) {
        Fraction before=cross(line[sz-2],line[sz-1]);
        Fraction now=cross(line[sz-1],l);
        if (cmp(before,now)) {
            break;
        }
        sz--;
    }
    line[sz++]=l;
}

long long cost(int l,int r) {
    long long minus=0;
    if (l!=0&&arr[l-1].second-arr[l].first+2>0) {
        minus=(arr[l-1].second-arr[l].first+2)*(arr[l-1].second-arr[l].first+2);
    }
    long long ret=(arr[r].second-arr[l].first+2)*(arr[r].second-arr[l].first+2);
    ret-=minus;
    return ret*2;
}

long long value;
int cut;
 
void getans(long long pen) {
    sz=0;
    ind=0;
    for(int i=0;i<n;i++) {
        if (i>0) {
            long long minus=0;
            if (arr[i-1].second-arr[i].first+2>0) {
                minus=(arr[i-1].second-arr[i].first+2)*(arr[i-1].second-arr[i].first+2);
            }
            insert({-4*arr[i].first,2*arr[i].first*arr[i].first-8*arr[i].first-minus*2+dp[i-1]+pen});
        }
        else {
            insert({-4*arr[i].first,2*arr[i].first*arr[i].first-8*arr[i].first+pen});
        }
        while (ind+1<sz&&cmp(cross(line[ind],line[ind+1]),{arr[i].second,1})) {
            ind++;
        }
        long long val;
        if (ind>=sz) {
            val=INF;
        }
        else {
            val=line[ind].a*arr[i].second+line[ind].b+2*(arr[i].second+2)*(arr[i].second+2);
        }
        dp[i]=val;
    }
    int now=n-1;
    int cnt=0;
    while (now!=-1) {
        for(int i=now;i>=0;i--) {
            long long val;
            if (i==0) {
                val=0;
            }
            else {
                val=dp[i-1];
            }
            if (val+cost(i,now)+pen==dp[now]) {
                now=i-1;
                cnt++;
                break;
            }
            if (i==0) {
                printf(".\n");
                now=-1;
            }
        }
    }
    value=dp[n-1];
    cut=cnt;
}
 
bool comp(P a,P b) {
    if (a.second==b.second) {
        return a.first<b.first;
    }
    return a.second<b.second;
}
 
long long take_photos(int nn,int mm,int kk,vector<int> r,vector<int> c) {
    n=nn;
    m=mm;
    k=kk;
    for(int i=0;i<n;i++) {
        if (r[i]>c[i]) {
            swap(r[i],c[i]);
        }
        temp[i]=P(2*r[i]+1,2*c[i]+1);
    }
    sort(temp,temp+n,comp);
    int s=0;
    long long mini=1e8;
    for(int i=n-1;i>=0;i--) {
        if (temp[i].first<mini) {
            arr[s++]=temp[i];
        }
        mini=min(mini,temp[i].first);
    }
    n=s;
    reverse(arr,arr+n);
    long long lo=-1;
    long long hi=8*m*m+13; //(lo,hi]
    while (lo+1<hi) {
        long long mid=lo+(hi-lo)/2;
        getans(2*mid+1);
        if (k<=cut) {
            lo=mid;
        }
        else {
            hi=mid;
        }
    }
    getans(2*hi);
    if ((value-2*k*hi)%8!=0) {
        return r[-1000000];
    }
    return (value-2*k*hi)/8;
}

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