Submission #588035

#	Time	Username	Problem	Language	Result	Execution time	Memory
588035		georgievskiy	Aliens (IOI16_aliens)	C++17	60 / 100	2101 ms	358004 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 inf = 2e18;

void calc(int l, int r, int opt_l, int opt_r, int j, vector<int>& x, vector<int>& y, vector<int>& t, vector<vector<int>>& d) {
    if (l > r) return;
    int opt = opt_l;
    int i = (l + r) / 2;
    for (int f = opt_l; f <= min(i - 1, opt_r); f++) {
        ll c = d[f][j - 1] + sqr(x[i - 1] - y[f] + 1) - t[f];
        if (c < d[i][j])
            d[i][j] = c, opt = f;
    }

    calc(l, i - 1, opt_l, opt, j, x, y, t, d);
    calc(i + 1, r, opt, opt_r, j, x, y, t, d);
}

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(), [](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();
    k = min(k, n);
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++)
        x[i] = st[i].first, y[i] = st[i].second;

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

    vector<vector<int>> d(n + 1, vector<int>(k + 1, inf));
    for (int j = 0; j <= k; j++)
        d[0][j] = 0;

    for (int j = 1; j <= k; j++)
        calc(1, n, 0, n, j, x, y, t, d);

    return d.back().back();
}

Compilation message (stderr)

aliens.cpp: In lambda function:
aliens.cpp:27:95: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   27 |     sort(a.begin(), a.end(), [](pii a, pii b) {return a.first < b.first || a.first == b.first && a.second > b.second;});
      |                                                                            ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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