Submission #419962

#	Time	Username	Problem	Language	Result	Execution time	Memory
419962		jhnah917	Aliens (IOI16_aliens)	C++14	100 / 100	122 ms	8788 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using PLL = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

inline ll sq(ll v){ return v*v; }

struct Line{
    ll a, b, i;
    Line() : Line(0, INF, 0) {}
    Line(ll a, ll b, ll i) : a(a), b(b), i(i) {}
    ll f(ll x) const { return a * x + b; }
};

struct CHT{
    Line v[101010]; int pv, top;
    void clear(){ pv = top = 0; }
    int __cross(const Line &a, const Line &b, const Line &c){
        return (a.a-c.a) * (b.b-a.b) >= (a.a-b.a) * (c.b-a.b);
    }
    void update(Line l){
        while(top >= pv+2 && __cross(v[top-2], v[top-1], l)) top--;
        v[top++] = l;
    }
    void update(ll a, ll b, ll c){ update({a, b, c}); }
    PLL query(ll x){
        while(pv+1 < top && v[pv].f(x) >= v[pv+1].f(x)) pv++;
        return {v[pv].f(x), v[pv].i};
    }
} cht;

int N, K;
PLL A[101010];
ll D[101010], C[101010];

void init(int _n, int _m, int _k, const vector<int> &_r, const vector<int> &_c){
    K = _k;
    vector<PLL> pts;
    for(int i=0; i<_n; i++) pts.emplace_back(min(_r[i], _c[i]), max(_r[i], _c[i]));
    sort(all(pts), [&](const PLL &p1, const PLL &p2){
        if(p1.x != p2.x) return p1.x < p2.x;
        return p1.y > p2.y;
    });
    N = 0;
    ll y = -INF;
    for(const auto &i : pts){
        if(y >= i.y) continue;
        A[++N] = i; y = i.y;
    }
}

ll get(ll c){
    cht.clear();
    cht.update(-2*A[1].x, sq(A[1].x) - 2*A[1].x, 0);
    for(int i=1; i<=N; i++){
        auto res = cht.query(A[i].y);
        D[i] = res.x + sq(A[i].y+1) + c;
        C[i] = C[res.y] + 1;
        cht.update(-2*A[i+1].x, D[i] + sq(A[i+1].x) -2*A[i+1].x - sq(max(0LL, A[i].y-A[i+1].x+1)), i);
    }
    return C[N];
}

ll take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c){
    init(_n, _m, _k, _r, _c);
    K = min(N, K);

    ll l = 0, r = 1e15, ans = 0;
    while(l <= r){
        ll m = l + r >> 1, cnt = get(m);
        if(cnt == K) return D[N] - K*m;
        else if(cnt < K) r = m - 1;
        else l = m + 1, ans = max(ans, D[N] - K*m);
    }
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:75:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         ll m = l + r >> 1, cnt = get(m);
      |                ~~^~~

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