Submission #587957

#	Time	Username	Problem	Language	Result	Execution time	Memory
587957		georgievskiy	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	724 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;
const int inf = 2e18;
ll d[N][K], opt[N][K];
ll t[N];

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() /*k=,[](pii a, pii b) {return a.first < b.first || a.first == b.first && a.second > b.second;}*/);
    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;

    for (int i = 0; i < n; i++) {
        for (int w = k; w >= 0; w--) {
            int l = 0, r = i;
            if (i)
                l = opt[i - 1][w];
            if (w + 1 <= n)
                r = opt[i][w + 1];
            for (int j = l; j <= r; j++) {
                ll c = sqr(x[i] + 1) - 2 * (x[i] + 1) * y[j] + t[j];
                if (j)
                    c += d[j - 1][w - 1];
                if (c < d[i][w])
                    d[i][w] = c, opt[i][w] = j;
            }
        }
    }

    return d[n - 1][k];
}

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