Submission #224855

#	Time	Username	Problem	Language	Result	Execution time	Memory
224855		urd05	Aliens (IOI16_aliens)	C++14	60 / 100	2089 ms	7928 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.
long long now[100005];
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) {
    return one.up*two.down<two.up*one.down;
}
 
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;
}
 
void getans() {
    sz=0;
    ind=0;
    for(int i=0;i<n;i++) {
        if (i>0&&dp[i-1]<=100000000000000LL) {
            long long minus=0;
            if (i>0&&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({-2*arr[i].first,arr[i].first*arr[i].first-4*arr[i].first-minus+dp[i-1]});
        }
        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+(arr[i].second+2)*(arr[i].second+2);
        }
        now[i]=val;
    }
}
 
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);
    for(int i=0;i<n;i++) {
        dp[i]=(-2*arr[0].first*arr[i].second+arr[0].first*arr[0].first-4*arr[0].first+(arr[i].second+2)*(arr[i].second+2));
    }
    long long ret=dp[n-1];
    for(int i=2;i<=k;i++) {
        getans();
        for(int j=0;j<n;j++) {
            dp[j]=now[j];
        }
        ret=min(ret,dp[n-1]);
    }
    return ret/4;
}

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