Submission #538567

#	Time	Username	Problem	Language	Result	Execution time	Memory
538567		KoD	Aliens (IOI16_aliens)	C++17	100 / 100	385 ms	4184 KiB

aliens

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

using ll = long long;
using std::vector;
using std::pair;

ll floor_div(const ll a, const ll b) {
    const ll q = a / b;
    const ll r = a - b * q;
    return r >= 0 ? q : q - 1;
}

struct Line {
    ll a, b;
    ll eval(const ll x) const {
        return a * x + b;
    }
};

struct CHT {
    std::deque<Line> line;
    ll change(const Line s, const Line t) const {
        return floor_div(t.b - s.b, s.a - t.a);
    }
    void add(const Line l) {
        int size = line.size();
        while (size >= 2) {
            const Line m = line[size - 1], n = line[size - 2]; 
            if (change(n, m) >= change(m, l)) {
                line.pop_back();
                size -= 1;
            } else {
                break;
            }
        }
        line.push_back(l);
    }
    ll get(const ll x) {
        while (line.size() >= 2 and line[0].eval(x) > line[1].eval(x)) {
            line.pop_front();
        }
        return line[0].eval(x);
    }
};

constexpr ll inf = 1000000000000;

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector<pair<int, int>> lr(n);
    for (int i = 0; i < n; ++i) {
        lr[i] = std::minmax(r[i], c[i]);
        lr[i].second += 1;
    }
    std::sort(lr.begin(), lr.end());
    vector<pair<int, int>> need;
    for (const auto& [l, r] : lr) {
        if (need.empty()) {
            need.emplace_back(l, r);   
        } else {
            auto& [a, b] = need.back();
            if (a == l) {
                b = r;
            } else if (b < r) {
                need.emplace_back(l, r);
            }
        }
    }
    n = need.size();
    k = std::min(k, n);
    const auto solve = [&](const ll lambda) {
        ll last = 0;
        CHT cht;
        for (int i = 0; i < n; ++i) {
            const auto& [l, r] = need[i];
            const ll dif = i == 0 ? 0 : need[i - 1].second - l;
            cht.add({-2 * l, (ll)l * l + last - (dif > 0 ? dif * dif : 0)});
            last = cht.get(r) + (ll)r * r + lambda;
        }
        return last - lambda * k;
    };
    ll min = -1, max = inf + 1; 
    while (max - min > 2) {
        const ll m1 = min + (max - min) / 2;
        const ll m2 = m1 + 1;
        if (solve(m1) >= solve(m2)) {
            max = m2;
        } else {
            min = m1;
        }
    }
    return solve(min + 1);
}

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