Submission #162837

#	Time	Username	Problem	Language	Result	Execution time	Memory
162837		rama_pang	Aliens (IOI16_aliens)	C++14	60 / 100	2085 ms	685076 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define NO_DEBUG
using namespace std;
using lint = long long;
const lint INF = 1e15;

struct Segment {
    lint left, right;

    Segment(lint l = 0, lint r = 0): left(l), right(r) {}

    bool operator < (const Segment &o) const {
        return left < o.left || (left == o.left && right > o.right);
    }

    bool operator == (const Segment &o) const {
        return left == o.left && right == o.right;
    }

};

struct ConvexHull { // Convex Hull Trick
    struct Line {
        lint m, c;
        int id;

        Line(lint M = 0, lint C = INF, int id_ = -1): m(M), c(C), id(id_) {}

        lint get(lint x) {
            return m * x + c;
        }

    };

    vector<Line> hull = {Line(0, INF)};
    
    int ptr = 0;

    void insert(lint m, lint c) {
        hull.emplace_back(Line(m, c));
        int sz = hull.size() - 1;

        /*  y = m1x + c1 = m2x + c2
            (m1 - m2)x = (c2 - c1)
            x = (c2 - c1) / (m1 - m2)

            (c2 - c1) / (m1 - m2) < (c3 - c2) / (m2 - m3) 

        */

        while (ptr <= sz - 2 && (hull[sz - 1].c - hull[sz].c) * (hull[sz - 1].m - hull[sz - 2].m) < 
                                (hull[sz - 2].c - hull[sz - 1].c) * (hull[sz].m - hull[sz - 1].m)) 
            hull[sz - 1] = hull[sz], sz--, hull.pop_back();

    }

    lint query(lint x) {
        while (ptr + 1 < hull.size() && hull[ptr].get(x) > hull[ptr + 1].get(x))
            ptr++;

        return hull[ptr].get(x) + x * x;
    }

};

int N, K;
vector<Segment> segment;
vector<vector<lint>> DP;
vector<ConvexHull> hull;

void preprocess(int n, int k, vector<int> r, vector<int> c) {
    for (int i = 0; i < n; i++) 
        segment.emplace_back(min(r[i], c[i]), max(r[i], c[i]));

    sort(segment.begin(), segment.end());

    vector<Segment> tmp;
    tmp.emplace_back(-1, -1);
    
    for (auto s : segment) {
        Segment overlap = Segment(min(tmp.back().left, s.left), max(tmp.back().right, s.right));
        if (overlap == s) swap(s, tmp.back());
        if (overlap == tmp.back()) continue;
        tmp.emplace_back(s);
    }

    segment = tmp, N = segment.size() - 1, K = k;
    DP.assign(N + 1, vector<lint>(K + 1, INF));
    hull.resize(K + 1);
}

lint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    preprocess(n, k, r, c);

    for (int k = 0; k <= K; k++)
        DP[0][k] = 0;
        
    for (int k = 1; k <= K; k++) {
        for (int n = 1; n <= N; n++) {
            lint m = - 2 * segment[n].left;
            lint c = + segment[n].left * segment[n].left 
                     - max(0ll, segment[n - 1].right - segment[n].left + 1) * 
                       max(0ll, segment[n - 1].right - segment[n].left + 1)
                     + DP[n - 1][k - 1];

            hull[k].insert(m, c);

            DP[n][k] = min(DP[n][k], hull[k].query(segment[n].right + 1));
        }
    }

    #ifndef NO_DEBUG
        for (int i = 0; i <= K; i++) {
            cout << "K = " << i << ": ";
            for (int j = 0; j <= N; j++) {
                cout << DP[j][i] << " ";
            }
            cout << "\n";
        }
    #endif


    return DP[N][K];

}

Compilation message (stderr)

aliens.cpp: In member function 'lint ConvexHull::query(lint)':
aliens.cpp:59:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (ptr + 1 < hull.size() && hull[ptr].get(x) > hull[ptr + 1].get(x))
                ~~~~~~~~^~~~~~~~~~~~~

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