제출 #926734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
926734		MtSaka	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	348 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 RMQ{
    private:
    int sz;
    vector<ll>seg;
    public:
    RMQ(int n):sz(1){
        while(sz<n)sz<<=1;
        seg.resize(sz<<1,inf);
    }
    RMQ(const vector<ll>&v):sz(1){
        while(sz<(int)v.size())sz<<=1;
        seg.resize(sz<<1,inf);
        rep(i,v.size())seg[i+sz]=v[i];
        rrep(i,sz)seg[i]=min(seg[i<<1],seg[i<<1^1]);
    }
    ll prod(int l,int r)const{
        l+=sz,r+=sz;
        ll ret=inf;
        while(l!=r){
            if(l&1)chmin(ret,seg[l++]);
            if(r&1)chmin(ret,seg[--r]);
            l>>=1,r>>=1;
        }
        return ret;
    }
};
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 v(m,inf);
    rep(i,n)chmin(v[c[i]],r[i]);
    RMQ rmq(v);
    auto cost=[&](ll l,ll r)->ll {
        ll mi=rmq.prod(l,r);
        if(mi>=r)return 0LL;
        return (r-mi)*(r-mi);
    };
    auto f=[&](ll lambda)->pair<ll,ll> {
        vector<pair<ll,ll>>dp(m+1,{inf,inf});
        dp[0]={0,0};
        vl idx(m+1,0);
        auto check=[&](ll l,ll r)->void {
            if(chmin(dp[r],pair<ll,ll>{dp[l].first+cost(l,r)+lambda,dp[l].second+1})){
                idx[r]=l;
            }
        };
        auto rec=[&](auto&&rec,ll l,ll r)->void {
            if(r-l<=1)return;
            ll mid=(l+r)/2;
            rep(i,idx[l],idx[r]+1)check(i,mid);
            rec(rec,l,mid);
            rep(i,l,mid+1)check(i,r);
            rec(rec,mid,r);
        };
        check(0,m);
        rec(rec,0,m);
        return dp[m];
    };
    ll ng=-1,ok=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);
    return val-k*ok;
}

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