Submission #1023493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023493		amirhoseinfar1385	Aliens (IOI16_aliens)	C++17	12 / 100	15 ms	956 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxk=100+10;
long long dp[maxn][maxk],n,m,k,cost[maxn],inf=1e14;

struct cht{
    long long inersect(pair<long long ,long long>a,pair<long long ,long long>b){
        long long sor=a.first-b.first,makh=b.second-a.second;
        if(makh==0){
            if(sor>0){
                return -inf;
            }
            return inf;
        }
        if(makh<0){
            sor*=-1;
            makh*=-1;
        }
        if(sor<0){
            return sor/makh;
        }
        return (sor+makh-1)/makh;
    }
    vector<pair<long long ,pair<long long ,long long>>>st;
    void clear(){
        st.clear();
    }
    void ins(pair<long long,long long>a){
        while((int)st.size()>0){
            long long x=inersect(a,st.back().second);
            if(x<=st.back().first){
                st.pop_back();
                continue;
            }
            st.push_back(make_pair(x,a));
            return ;
        }
        st.push_back(make_pair(-inf,a));
    }
    long long pors(long long x){
        if(st.size()==0){
            return -inf;
        }
        int p=lower_bound(st.begin(),st.end(),make_pair(x+1,make_pair(-inf,-inf)))-st.begin();
        p--;
        return st[p].second.first+x*st[p].second.second;
    }
}cht;

long long take_photos(int n_, int m_, int k_, std::vector<int> r, std::vector<int> c) {
    n=n_;
    m=m_;
    k=k_;
    vector<pair<long long,long long>>allv;
    allv.resize(n);
    for(int i=0;i<n;i++){
        allv[i]=make_pair(r[i],c[i]);
        if(allv[i].first>allv[i].second){
            swap(allv[i].first,allv[i].second);
        }
        allv[i].second=-allv[i].second;
    }
    sort(allv.begin(),allv.end());
    vector<pair<long long,long long>>fake;
    for(int i=0;i<n;i++){
        allv[i].second*=-1;
        if(i==0||fake.back().second-(allv[i].first-fake.back().first)<allv[i].second){
            fake.push_back(allv[i]);
        }
    }
    allv=fake;
    n=(int)fake.size();
    for(int i=0;i<=n;i++){
        dp[i][0]=inf;
    }
    for(int i=1;i<n;i++){
        long long c=max(-1ll,allv[i-1].second-allv[i].first);
        c++;
        c*=c;
        cost[i]=c;
    }
   // dp[0][0]=(allv[0].second-allv[0].first+1)*(allv[0].second-allv[0].first+1);
    for(int lev=1;lev<=k;lev++){
        cht.clear();
        dp[0][lev]=inf;
        vector<vector<int>>addy(n+1);
        for(int i=0;i<n;i++){
            if(i>0){
                //int p=lower_bound(allv.begin(),allv.end(),make_pair(allv[i].second,-1ll))-allv.begin();
                int p=i;
                if(allv[i].first==allv[i].second){
                    p=i;
                }
                addy[p].push_back(i);
            }   
            for(auto x:addy[i]){
                cht.ins(make_pair(-dp[x-1][lev-1]+cost[x]-(allv[x].first-1)*(allv[x].first-1),allv[x].first-1));
            }
            dp[i][lev]=cht.pors(2*allv[i].second)-allv[i].second*allv[i].second;
            dp[i][lev]=-dp[i][lev];
       //     cout<<i<<" "<<lev<<" "<<dp[i][lev]<<endl;
            if(dp[i][lev]>=inf){
                dp[i][lev]=min(dp[i][lev],1ll*(allv[i].second-allv[0].first+1)*(allv[i].second-allv[0].first+1));
            }
         //   cout<<i<<" "<<lev<<" "<<dp[i][lev]<<endl;
        }
        for(auto x:addy[n]){
         cht.ins(make_pair(-dp[x-1][k-1]+cost[x]-(allv[x].first-1)*(allv[x].first-1),allv[x].first-1));
        }
    }
    long long te=allv[n-1].second;
    long long mainres=cht.pors(2*allv[n-1].second)-(te*te);
    mainres=-mainres;
    if(mainres>=inf){
        mainres=1ll*(te-(allv[0].first)+1)*(te-(allv[0].first)+1);
    }
    mainres=dp[n-1][k];
    return mainres;
}

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