Submission #586055

#	Time	Username	Problem	Language	Result	Execution time	Memory
586055		georgievskiy	Aliens (IOI16_aliens)	C++17	4 / 100	9 ms	2620 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define sqr(x) ((x)*(x))
using pii = pair<int, int>;

const int N = 4001, K = 4001, M = 1e6+100;
const int inf = 2e18;
ll d[N][K];
ll t[N];
/*
struct line {
    int k, b;
    line () {
        k = 0, b = inf;
    }
    line(int k, int b) : k(k), b(b) {}
    int get(int x) {
        return k * x + b;
    }
};

struct LiChao {
    line t[4 * M];

    void add(int v, int tl, int tr, line q) {
        int m = (tl + tr) / 2;
        bool bl = q.get(tl) < t[v].get(tl), br = q.get(tr) < t[v].get(tr), bm = q.get(m) < t[v].get(m);
        if (!bl && !br)
            return;
        if (bl && br) {
            t[v] = q;
            return;
        }
        if (bl != bm) {
            line p = t[v];
            t[v] = q;
            add(2 * v + 1, tl, m, p);
        } else {
            line p = t[v];
            t[v] = q;
            add(2 * v + 2, m, tr, p);
        }
    }

    int get(int v, int tl, int tr, int x) {
        if (tl + 1 == tr)
            return t[v].get(x);
        int d, m = (tl + tr) / 2;
        if (x < m)
            d = get(2 * v + 1, tl, m, x);
        else
            d = get(2 * v + 2, m, tr, x);
        return min(d, t[v].get(x));
    }

};
*/

long long f(vector<int>&x , vector<int>& y, int lambda, int& k) {
    int n = x.size();
    vector<int> d(n, inf), s(n, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            ll c = sqr(x[i] + 1) - 2 * (x[i] + 1) * y[j] + t[j];
            int prev = 0, seg = 0;
            if (j) prev = d[j - 1], seg = s[j - 1];
            int x = prev + c + lambda;
            if (d[i] > x)
                d[i] = x, s[i] = seg+1;
        }
    }
    k = s.back();
    return d.back();
}

long long take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c) {
    vector<pii> a(n);
    for (int i = 0; i < n; i++) a[i] = {max(r[i], c[i]), min(r[i], c[i])};
    sort(a.begin(), a.end());
    vector<pii> st;
    for (pii p : a) {
        while (st.size() && st.back().second >= p.second)
            st.pop_back();
        st.push_back(p);
    }
    n = st.size();
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++)
        x[i] = st[i].first, y[i] = st[i].second;

    for (int i = 0; i < n; i++) {
        if (i)
            t[i] = max(0ll, x[i - 1] - y[i] + 1);
        t[i] = sqr(t[i]);
        t[i] = sqr(y[i]) - t[i];
    }

    for (int i = 0; i < n; i++)
        for (int w = 0; w <= k; w++)
            d[i][w] = inf;

    k = min(k, n);

    int lo = -1, hi = 1e11;
    while (hi - lo > 1) {
        int c = (hi + lo) / 2;
        int seg = 0;
        f(x, y, c, seg);
        if (seg > k)
            lo = c;
        else
            hi = c;
    }
    int t;
    int ans = f(x, y, hi, t);
    ans -= hi * t;
    return ans;
}

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