Submission #731818

#	Time	Username	Problem	Language	Result	Execution time	Memory
731818		vjudge1	Aliens (IOI16_aliens)	C++11	60 / 100	2065 ms	19388 KiB

aliens

#include "aliens.h"

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

class cht_t {
       public:
        class line_t {
               public:
                int64_t a, b;
                line_t(int64_t a = 0, int64_t b = 0) : a(a), b(b) {}
                int64_t operator()(const int64_t& x) const {
                        return a * x + b;
                }
                friend bool check(const line_t& lhs, const line_t& rhs, const line_t& cur) {
                        return 1.0 * (rhs.b - cur.b) / (cur.a - rhs.a) < 1.0 * (lhs.b - cur.b) / (cur.a - lhs.a);
                        return (rhs.b - cur.b) * (cur.a - lhs.a) < (lhs.b - cur.b) * (cur.a - lhs.a);
                }
        };
        deque<line_t> dq;
        void insert(const int64_t& a, const int64_t& b) {
                line_t new_line(a, b);
                while (dq.size() > 1 && check(dq[dq.size() - 2], dq.back(), new_line)) {
                        dq.pop_back();
                }
                dq.emplace_back(new_line);
        }

        int64_t get_min(const int64_t& x) {
                while (dq.size() > 1 && dq[0](x) > dq[1](x)) dq.pop_front();
                return dq[0](x);
        }
};

long long take_photos(int n, int m, int k, std::vector<int> a, std::vector<int> b) {
        for (int i = 0; i < n; i++) {
                if (a[i] > b[i]) swap(a[i], b[i]);
        }
        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
                return a[i] == a[j] ? b[i] > b[j] : a[i] < a[j];
        });
        vector<int> l, r;
        int last = -1;
        for (int i = 0; i < n; i++) {
                if (b[ord[i]] <= last) continue;
                l.emplace_back(a[ord[i]] - 1);
                r.emplace_back(b[ord[i]]);
                last = b[ord[i]];
        }

        n = l.size();
        k = min(k, n);

        auto cost = [](int l, int r) {
                if (l > r) return 0ll;
                return 1ll * (r - l) * (r - l);
        };

        vector<cht_t> cht(k - 1);

        int64_t f;

        for (int i = 0; i < n; i++) {
                for (int j = min(i, k - 1); j >= 0; j--) {
                        if (i + k - j > n) continue;
                        f = j ? cht[j - 1].get_min(r[i]) + 1ll * r[i] * r[i] : cost(l[0], r[i]);
                        if (i + 1 < n && j != k - 1) cht[j].insert(-2 * l[i + 1], f + 1ll * l[i + 1] * l[i + 1] - cost(l[i + 1], r[i]));
                }
        }

        return f;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:73:16: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |         return f;
      |                ^

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