Submission #500454

#	Time	Username	Problem	Language	Result	Execution time	Memory
500454		dooompy	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	204 KiB

aliens

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

using namespace std;


template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

#define ll long long

struct line {
    ll m, c; int id;

    ll eval(ll x) {
        return m * x + c;
    }

    long double intersectX(line o) const {
        return (long double) (c - o.c) / (o.m - m);
    }
};

vector<pair<int, int>> points;

pair<ll, ll> ct(ll c) {
    deque<line> dq;

    dq.push_back({-2 * points[0].first, points[0].first * points[0].first - 2  * points[0].first, 0});

    int n= points.size();
    vector<int> ct(n + 5);
    vector<ll> dp(n + 5);

    for (int i = 0; i < n; i++) {
        while (dq.size() >= 2 && dq[0].eval(points[i].second) >= dq[1].eval(points[i].second)) dq.pop_front();

        ll cur = dq.front().eval(points[i].second) + (points[i].second + 1) * (points[i].second + 1) + c;
        dp[i] = cur;
        ct[i + 1] = ct[dq.front().id] + 1;

        if (i == n-1) break;

        line l = {-2 * points[i+1].first, points[i + 1].first * points[i + 1].first - 2 * points[i + 1].first + dp[i] - max(points[i].second - points[i + 1].first + 1, 0) * max(points[i].second - points[i + 1].first + 1, 0), i + 1};

        while (dq.size() >= 2 && l.intersectX(dq.back()) <= dq.back().intersectX(dq[dq.size() - 2])) dq.pop_back();
        dq.push_back(l);
    }

    return {ct[n], dp[n-1]};
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {

    for (int i = 0; i < n; i++) {
        if (r[i] > c[i]) swap(r[i], c[i]);
        points.emplace_back(r[i], c[i]);
    }

    sort(points.begin(), points.end(), [](pair<int, int> a, pair<int, int> b) {
        if (a.second == b.second) {
            return a.first > b.first;
        } else return a.second < b.second;
    });

    vector<pair<int, int>> final;

    for (int i = 0; i < n; i++) {
        while (!final.empty() && final.back().first >= points[i].first) final.pop_back();
        final.push_back(points[i]);

    }

    points = final;

    test(points);

    ll left = 0, right = (ll) m * m;

    k = min(k, (int) points.size());

    while (left != right) {
        ll mid = (left + right) / 2;
        auto cur = ct(mid);
        if (cur.first == k) return cur.second - mid * k;
        if (cur.first > k) left = mid + 1;
        else right = mid;
    }

    auto ans = ct(left);

    return ans.second  - left * k;
}

//int main() {
//    take_photos(2, 2, 1, {0, 1}, {0, 1});
//
//}

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