Submission #1285492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285492		_callmelucian	Aliens (IOI16_aliens)	C++17	0 / 100	2 ms	352 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct line {
    ll a, b, idx;

    line() : a(0), b(0), idx(0) {}
    line (ll a, ll b, ll idx) : a(a), b(b), idx(idx) {}

    pl calc (ll x) { return {a * x + b, idx}; }
    friend double xsect (line X, line Y) {
        return double(X.b - Y.b) / double(Y.a - X.a);
    }
};

struct CHT : deque<line> {
    line get (int x) {
        if (x >= 0 && x >= size()) exit(10);
        if (x < 0 && (int)size() - x < 0) exit(26);
        return (x >= 0 ? at(x) : at((int)size() - x));
    }

    void push (line cur) {
        while (size() >= 2 && xsect(get(-2), get(-1)) >= xsect(get(-1), cur)) pop_back();
        return push_back(cur);
    }

    pl query (ll x) {
        while (size() >= 2 && x >= xsect(get(0), get(1))) pop_front();
        return size() ? front().calc(x) : make_pair(LLONG_MAX, LLONG_MAX);
    }
};

pl solveDP (ll penalty, const vector<pii> &intervals) {
    int n = intervals.size();
    vector<pl> dp(n);

    function<ll(ll)> sq = [&] (ll a) { return a * a; };
    if (intervals.empty()) exit(21);

    // prepare convex hull trick
    CHT hull;
    hull.push(line(-2 * intervals[0].first, sq(intervals[0].first), 0));

    // run dp, the cost of opening a new group is `penalty`
    for (int i = 0; i < n; i++) {
        int L, R; tie(L, R) = intervals[i];
        dp[i] = hull.query(R);
        if (dp[i].first != LLONG_MAX)
            dp[i].first += R * R + penalty, dp[i].second++;

        if (i + 1 < n) {
            ll nextL = intervals[i + 1].first, subtract = sq(max(0LL, R - nextL));
            hull.push(line(-2 * nextL, sq(nextL) + dp[i].first - subtract, dp[i].second));
        }
    }
    return dp[n - 1];
}

ll solve (int target, const vector<pii> &intervals) {
    target = min(target, (int)intervals.size());

    // binary search a suitable penalty value
    ll penalty = 0;
    for (ll mask = 1LL << 39; mask; mask >>= 1) {
        ll newPen = penalty | mask, value, partition;
        tie(value, partition) = solveDP(newPen, intervals);
        if (partition == target) return value - partition * newPen;
        if (partition > target) penalty = newPen;
    }
    return solveDP(0, intervals).first;
}

ll take_photos (int n, int m, int k, vector<int> r, vector<int> c) {
    // turn points on grid into intervals
    vector<pii> intervals;
    for (int i = 0; i < n; i++)
        intervals.emplace_back(min(r[i], c[i]) - 1, max(r[i], c[i]));
    
    // filter out all the intervals that is fully wrapped inside another
    sort(all(intervals), [&] (pii a, pii b) {
        if (a.first == b.first) return a.second > b.second;
        return a.first < b.first;
    });
    vector<pii> good;
    int far = INT_MIN;
    for (auto [L, R] : intervals)
        if (far < R) good.emplace_back(L, R), far = R;
    
    // solve
    return solve(k, good);
}

#ifdef LOCAL
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    vector<int> r = {0, 0, 0, 0, 0};
    vector<int> c = {1, 2, 3, 4, 5};

    cout << take_photos(5, 7, 2, r, c) << "\n";

    r = {1, 4};
    c = {4, 1};
    cout << take_photos(2, 6, 2, r, c) << "\n";

    return 0;
}
#endif

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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