Submission #1023998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023998		vjudge1	Aliens (IOI16_aliens)	C++17	60 / 100	159 ms	36296 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"

using namespace std;

#define sz(s) (int)s.size()
#define mem(a,i) memset(a,i,sizeof(a))
#define pb push_back
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define ll long long
#define F first
#define S second
#define ld long double
#define ppb pop_back

const int MAX=1e6+10;
const ll inf=2e18;

vector<int> vec[MAX];
vector<pair<ll,ll>> dp;
int n,m,k;

ll S(int x,int y){
    ll a=x-y+1;
    if(a<=0)return 0;
    return a*a;
}

ld inter(pair<ll,ll> a,pair<ll,ll> b){
    return (a.S-b.S)/(b.F-a.F);
}

struct cht{
    vector<pair<pair<ll,ll>,ll>> lines;
    int pos;

    void init(){
        lines.clear();
        pos=0;
    }

    void add(ll k,ll x,ll cnt){
        while(sz(lines)>1&&inter(lines[sz(lines)-2].F,lines.back().F)>inter(lines[sz(lines)-2].F,{k,x}))lines.ppb();
        lines.pb({{k,x},cnt});
        pos=min(pos,sz(lines)-1);
    }

    ll get(pair<ll,ll> a,ll x){
        return a.F*x+a.S;
    }

    pair<ll,ll> get(ll x){
        if(lines.empty()){
            return {inf,inf};
        }
        while(pos+1<sz(lines)&&get(lines[pos].F,x)>get(lines[pos+1].F,x)){
            pos++;
        }
        return {get(lines[pos].F,x),lines[pos].S};
    }
}C;
vector<pii> pts;

int check(ll c){
    C.init();
    for(int i=0;i<n;i++)dp[i].F=inf,dp[i].S=0;
    for(int i=0;i<n;i++){
        if(i-1>=0)C.add(-2*pts[i].S,dp[i-1].F+pts[i].S*1ll*pts[i].S-2*pts[i].S,dp[i-1].S);
        else C.add(-2*pts[i].S,+pts[i].S*1ll*pts[i].S-2*pts[i].S,0);
        dp[i]={C.get(pts[i].F).F+pts[i].F*1ll*pts[i].F+2*pts[i].F+1+c,C.get(pts[i].F).S+1};
        if(i!=n-1){
            dp[i].F-=S(pts[i].F,pts[i+1].S);
        }
        dp[i].F=min(dp[i].F,inf);
    }
    // cout<<dp[n-1].S<<"\n";
    return dp[n-1].S;
}

long long take_photos(int N, int M, int K, vector<int> r, vector<int> c) {
    n=N,m=M,k=K;
    vector<int> actr,actc;
    for(int i=0;i<n;i++){
        if(r[i]<c[i]){
            swap(c[i],r[i]);
        }
        vec[r[i]].pb(c[i]);
    }
    for(int i=0;i<m;i++)sort(all(vec[i]));
    stack<int> st;
    for(int i=0;i<m;i++){
        if(vec[i].empty())continue;
        while(!st.empty()&&vec[st.top()][0]>=vec[i][0]){
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty()){
        int x=st.top();
        pts.pb({x,vec[x][0]});
        st.pop();
    }
    reverse(all(pts));
    n=sz(pts);
    if(k>=n){
        ll ans=0;
        for(int i=0;i<n;i++){
            ans+=S(pts[i].F,pts[i].S);
            if(i!=n-1)ans-=S(pts[i].F,pts[i+1].S);
        }
        return ans;
    }
    dp.resize(n);

    ll res=1e13;

    for(ll l=-1e13,r=1e13;l<=r;){
        ll m=(l+r)/2;
        // cout<<m<<" "<<check(m)<<"\n";
        if(check(m)<=k){
            r=m-1;
            res=m;
        }
        else l=m+1;
    }


    // check(-1e8);

    // cout<<check(-1e8)<<" "<<check(0)<<" "<<check(res)<<" "<<check(1e8)<<"\n";

    check(res);
    // cout<<dp[n-1].F<<" "<<dp[n-1].S<<" "<<res<<"\n";
    return dp[n-1].F-k*(res);
}

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