Submission #995697

#	Time	Username	Problem	Language	Result	Execution time	Memory
995697		biank	Aliens (IOI16_aliens)	C++17	0 / 100	0 ms	376 KiB

aliens

#include <bits/stdc++.h>
 
using namespace std;
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
using ll = long long;
using ld = long double;
 
struct Line {
    ll m, b, k;
    ll operator()(ll x) {
        return m * x + b;
    }
    ll intersect(Line o) {
        return ceil((ld)(o.b - b) / (m - o.m));
    }
};
 
struct LineContainer : deque<pair<Line, ll>> {
    void add(ll m, ll b, ll k) {
        Line A = Line{m, b, k};
        while (!empty()) {
            auto [B, p] = back();
            if (A(p) <= B(p)) pop_back();
            else break;
        }
        ll p = 0;
        if (!empty()) {
            p = A.intersect(back().first);
        }
        emplace_back(A, p);
    }
    pair<ll,int> query(ll x) {
        while (size() > 1 && at(1).first(x) <= at(0).first(x)) {
            pop_back();
        }
        auto [l, p] = at(0);
        return {l(x), l.k};
    }
};

struct Point {
    ll x, y;
};
 
ll take_photos(int n, int /*m*/, int k, vector<int> R, vector<int> C) {
    vector<Point> v;
    for (int i = 0; i < n; i++) {
        if (R[i] > C[i]) swap(R[i], C[i]);
        v.push_back({R[i], C[i]});
    }
    sort(all(v), [](Point a, Point b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y > b.y;
    });
    vector<Point> p{{-1, -1}};
    for (int i = 0; i < n; i++) {
        if (v[i].y > p.back().y) p.push_back(v[i]);
    }
    n = sz(p);
    k = min(k, n);
    auto sq = [](ll x) { return x * x; };
    auto check = [&](ll lambda) {
        LineContainer dp;
        ll res = 0, cnt = 0;
        for (int i = 1; i < n; i++) {
            ll m = -2LL * (p[i].x - 1);
            ll b = res + sq(p[i].x - 1) - sq(max(p[i - 1].y - p[i].x + 1, 0LL));
            dp.add(m, b, cnt);
            tie(res, cnt) = dp.query(p[i].y);
            res += sq(p[i].y) + lambda;
            cnt++;
        }
        return pair<ll, ll>{res, cnt};
    };
    
    ll lo = 0, hi = 1e13;
    ll ans = 0;
    while (hi - lo > 1) {
        ll mid = (lo + hi) / 2;
        auto [res, cnt] = check(mid);
        if (cnt <= k) hi = mid, ans = res - k * mid;
        else lo = mid;
    }
    return ans;
}

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