Submission #1024150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024150		vjudge1	Aliens (IOI16_aliens)	C++17	4 / 100	10 ms	24156 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 (0.0+a.S-b.S)/(0.0+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){
        if(!lines.empty())assert(lines.back().F.F!=k);
        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){
        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++){
        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);
        }
    }
    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;
    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=0,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;
        }
    }
 
//36 749999988180
    // check(-1e8);
 
    // cout<<n<<" "<<check(-1e8)<<" "<<check(0)<<" "<<check(res)<<" "<<check(1e13)<<"\n";
    // cout<<res<<"\n";
    // cout<<check(36)<<"\n";
    check(res);
    // cout<<dp[n-1].F<<" "<<dp[n-1].S<<" "<<res<<"\n";
    return dp[n-1].F-dp[n-1].S*res;
}

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