Submission #69252

#	Time	Username	Problem	Language	Result	Execution time	Memory
69252		mr_banana	Aliens (IOI16_aliens)	C++17	4 / 100	4 ms	804 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
const int MN=5000+10;
long long inf;
long long dp[MN][MN];
pair<int,int> p[MN];
long long sq(long long x){
    return x*x;
}
int a[MN],b[MN];
int po,po1;
double cross(int i,int j){
    return 1.0*(a[i]-a[j])/(b[j]-b[i]);
}
int cht[MN];
void add(int i){
    while(po>=2 && cross(i,cht[po-2])<cross(cht[po-1],cht[po-2])){
        po--;
    }
    cht[po++]=i;
}
long long ans1(int x,int i){
    return 1ll*a[i]*x+b[i];
}
long long ans(int x){
    while(po1+1<po && ans1(x,cht[po1+1])<ans1(x,cht[po1])){
        po1++;
    }
    return ans1(x,cht[po1]);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    inf=sq(m);
    for(int i=0;i<n;i++){
        p[i]={min(r[i],c[i]),-max(r[i],c[i])-1};
    }
    sort(p,p+n);
    int n1=unique(p,p+n)-p;
    n=0;
    int mx=-1;
    for(int i=0;i<n1;i++){
        if(mx<-p[i].second){
            p[n]={p[i].first,-p[i].second};
            mx=p[n].second;
            n++;
        }
    }
    for(int i=0;i<n;i++){
        a[i]=-2*p[i].first;
        if(i!=0){
            dp[i][0]=inf;
        }
        b[i]=dp[i][0]+sq(p[i].first);
    }
    for(int j=1;j<=k;j++){
        po=0,po1=0;
        add(0);
        for(int i=1;i<=n;i++){
            dp[i][j]=sq(p[i-1].second)+ans(p[i-1].second);
            if(i<n){
                b[i]=dp[i][j-1]+sq(p[i].first)-sq(max(0,p[i-1].second-p[i].first));
                add(i);
            }
        }
    }
    return dp[n][k];
}

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