Submission #1041350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041350		noyancanturk	Aliens (IOI16_aliens)	C++17	100 / 100	122 ms	12232 KiB

aliens

#include "aliens.h"

#include<bits/stdc++.h>
using namespace std;

using lint=int64_t;
using pii=pair<lint,lint>;

#define pb push_back

struct cht{
    struct state{
        lint first,second,aux;
    };
    deque<state>st;
    void insert(lint a,lint b,lint aux){
        int sz;
        while(
            1<(sz=st.size())
            &&
            (st[1].second-b)*(st[0].first-st[1].first)
            <
            (a-st[1].first)*(st[1].second-st[0].second)
        ){
            st.pop_front();
        }
        st.push_front({a,b,aux});
    }
    pii query(lint x){
        int sz;
        while(
            1<(sz=st.size())
            &&
            st[sz-2].first*x+st[sz-2].second
            <
            st[sz-1].first*x+st[sz-1].second
        ){
            st.pop_back();
        }
        sz=st.size();
        lint res=st[sz-1].first*x+st[sz-1].second;
        return pii{res,st[sz-1].aux};
    }
};

long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> c) {
    for(int i=0;i<n;i++){
        if(c[i]<R[i]){
            swap(c[i],R[i]);
        }
    }
    int points[m+1];
    memset(points,-1,sizeof(points));
    for(int i=0;i<n;i++){
        points[R[i]]=max(points[R[i]],c[i]);
    }
    vector<pii>pts;
    for(int i=0;i<=m;i++){
        if(points[i]!=-1){
            if(!pts.size()||pts.back().second<points[i]){
                pts.pb(pii{i,points[i]});
            }
        }
    }
    n=pts.size();
    lint ans=LLONG_MAX;
    lint dp[n+1],aux[n+1],b[n+1];
    b[0]=(pts[0].first-1)*(pts[0].first-1);
    for(int i=1;i<=n;i++){
        if(i==n)b[i]=0;
        else{
            b[i]=-(pts[i].first<=pts[i-1].second?
                (pts[i-1].second-pts[i].first+1)*(pts[i-1].second-pts[i].first+1)
                :0)+(pts[i].first-1)*(pts[i].first-1);
        }
    }
    cht st;
    lint l=0,r=10000000000100,tr=r;
    while(l<=r){
        lint lambda=(l+r)>>1;
        st.st.clear();
        dp[0]=0;
        aux[0]=0;
        st.insert(-2*(pts[0].first-1),b[0],0);
        for(int i=1;i<=n;i++){
            lint y=pts[i-1].second;
            pii res=st.query(y);
            dp[i]=res.first+y*y+lambda;
            aux[i]=res.second+1;
            if(i<n)st.insert(-2*(pts[i].first-1),b[i]+dp[i],aux[i]);
        }
        if(aux[n]<=k){
            tr=lambda;
            r=lambda-1;
        }else{
            l=lambda+1;
        }
    }
    lint lambda=tr;
    st.st.clear();
    dp[0]=0;
    aux[0]=0;
    st.insert(-2*(pts[0].first-1),b[0],0);
    for(int i=1;i<=n;i++){
        lint y=pts[i-1].second;
        pii res=st.query(y);
        dp[i]=res.first+y*y+lambda;
        aux[i]=res.second+1;
        if(i<n)st.insert(-2*(pts[i].first-1),b[i]+dp[i],aux[i]);
    }
    return dp[n]-k*lambda;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:66:10: warning: unused variable 'ans' [-Wunused-variable]
   66 |     lint ans=LLONG_MAX;
      |          ^~~

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