Submission #926979

#	Time	Username	Problem	Language	Result	Execution time	Memory
926979		MtSaka	Aliens (IOI16_aliens)	C++17	100 / 100	249 ms	7108 KiB

aliens

#include<bits/stdc++.h>
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,l,r) for(ll i=(ll)l;i<(ll)r;++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)a-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
static constexpr ll mod1=998244353;
static constexpr ll mod=1000000007;
static constexpr ll inf=numeric_limits<ll>::max()/2;
using vl=vector<ll>;
struct CHT{
    private:
    deque<array<ll,3>>dq;
    ll floor_div(ll x,ll y){
        if(x>=0)return x/y;
        return x/y-(x%y?1:0);
    }
    bool need(array<ll,3>l1,array<ll,3>l2,array<ll,3>add){
        return floor_div(l2[1]-l1[1],l1[0]-l2[0])<floor_div(add[1]-l2[1],l2[0]-add[0]);
    }
    public:
    CHT():dq(){}
    void add(ll a,ll b,ll id){
        array<ll,3>l{a,b,id};
        while(dq.size()>=2&&!need(dq[dq.size()-2],dq[dq.size()-1],l)){
            dq.pop_back();
        }
        dq.emplace_back(l);
    }
    pair<ll,ll>get(ll x){
        if(dq.empty())return {inf,0};
        while(dq.size()>=2&&dq[0][0]*x+dq[0][1]>dq[1][0]*x+dq[1][1]){
            dq.pop_front();
        }
        return pair<ll,ll>{dq[0][0]*x+dq[0][1],dq[0][2]};
    }
};
ll take_photos(int n,int m,int k,vector<int>r,vector<int>c){
    rep(i,n)if(r[i]>c[i])swap(r[i],c[i]);
    vl idx(n);iota(all(idx),0);
    sort(all(idx),[&](ll i,ll j){return (r[i]!=r[j]?r[i]<r[j]:c[i]>c[j]);});
    vector<pair<ll,ll>>v;
    for(auto i:idx){
        if(v.empty()||v.back().second<=c[i]){    
            v.emplace_back(r[i],c[i]+1);
        }
    }
    n=v.size();
    chmin(k,n);
    auto cost=[&](ll i,ll j)->ll {
        if(i==j)return 0;
        if(j==0)return 0;
        return (v[j-1].second-v[i].first)*(v[j-1].second-v[i].first)-(i>0&&v[i-1].second>=v[i].first?(v[i-1].second-v[i].first)*(v[i-1].second-v[i].first):0);
    };
    auto f=[&](ll lambda)->pair<ll,ll> {
        vector<pair<ll,ll>>dp(n+1,{inf,inf});
        dp[0]={0,0};
        CHT cht;
        cht.add(-2*v[0].first,v[0].first*v[0].first,0);
        rep(i,1,n+1){
            auto [val,id]=cht.get(v[i-1].second);
            val+=v[i-1].second*v[i-1].second+lambda;
            dp[i]=pair<ll,ll>{val,id+1};
            if(i<n)cht.add(-2*v[i].first,val+v[i].first*v[i].first-(v[i-1].second>=v[i].first?(v[i-1].second-v[i].first)*(v[i-1].second-v[i].first):0),id+1);
        }
        return dp[n];
    };
    ll ng=-1,ok=(ll)m*m+1;
    while(ok-ng>1){
        ll mid=(ok+ng)/2;
        auto [val,x]=f(mid);
        //cerr<<mid<<" "<<val<<" "<<x<<endl;
        if(x>k)ng=mid;
        else ok=mid;
    }
    auto [val,x]=f(ok);
    ll ans=val-ok*k;
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:63:10: warning: variable 'cost' set but not used [-Wunused-but-set-variable]
   63 |     auto cost=[&](ll i,ll j)->ll {
      |          ^~~~

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