Submission #778642

#	Time	Username	Problem	Language	Result	Execution time	Memory
778642		doowey	Aliens (IOI16_aliens)	C++14	100 / 100	239 ms	12716 KiB

aliens

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair

const ld inf = (ld)1e18;


struct line{
    ll ai;
    ll bi;
    int cn;
    ld lim;
};

vector<line> hull;

ld inter(line aa, line bb){
    return (ld)(aa.bi - bb.bi) / (ld)(bb.ai - aa.ai);
}

void put_line(ll aa, ll bb, int c){
    aa=-aa;
    bb=-bb; // assume a is increasing
    line nw = {aa, bb, c, inf};
    line l1, l2;
    while(hull.size() >= 2){
        l1 = hull[hull.size() - 2];
        l2 = hull[hull.size() - 1];
        if(inter(l1, l2) >= inter(l2, nw)) {
            hull.pop_back();
        }
        else{
            break;
        }
    }
    if(!hull.empty()) hull.back().lim=inter(hull.back(), nw);
    hull.push_back(nw);
}

pair<ll, int> query(ll xi){
    int l = 0;
    int r = (int)hull.size() - 1;
    int mid;
    while(l < r){
        mid = (l + r) / 2;
        if(hull[mid].lim < xi){
            l=mid + 1;
        }
        else{
            r=mid;
        }
    }
    return mp(-xi * 1ll * hull[l].ai - hull[l].bi, hull[l].cn);
}

const int N = (int)1e5 + 10;
vector<pii> T;
ll dp[N];
int cnt[N];

ll sq(ll x){
    return x * 1ll * x;
}

void compute(int n, int k, ll penalty){
    dp[0]=cnt[0]=0;
    hull.clear();
    for(int i = 1; i < n; i ++ ){
        dp[i]=inf;
    }
    ll B;
    pair<ll, int> ndp;
    for(int i = 1 ; i < n; i ++ ){
        B = sq(max(T[i - 1].se - T[i].fi, 0));
        put_line(-2ll * T[i].fi, sq(T[i].fi) + dp[i - 1] - B, cnt[i - 1]);
        ndp = query(T[i].se);
        ndp.fi += sq(T[i].se) + penalty;
        ndp.se ++ ;
        dp[i] = ndp.fi;
        cnt[i] = ndp.se;
    }
}


ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector<pii> segt;
    for(int i = 0 ; i < n ; i ++ ){
        segt.push_back(mp(min(r[i], c[i]), max(r[i],c[i])));
    }
    sort(segt.begin(), segt.end(), [&](pii i, pii j){
        if(i.fi == j.fi){
            return i.se > j.se;
        }
        else{
            return i.fi < j.fi;
        }
    });
    T.push_back(mp(-1,-1));
    for(auto x : segt){
        if(x.se > T.back().se){
            T.push_back(x);
        }
    }
    n=T.size();
    for(int i = 1; i < n; i ++ ) T[i].fi -- ;
    k=min(k,n-1);
    ll lf = 0ll, rf = m * 1ll * m + 100;
    ll mid;
    while(lf < rf){
        mid = (lf + rf) / 2;
        compute(n, k, mid);
        if(cnt[n - 1] <= k){
            rf=mid;
        }
        else{
            lf=mid+1;
        }
    }
    compute(n, k, lf);
    return dp[n-1] - k * 1ll * lf;
}

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