Submission #587992

#	Time	Username	Problem	Language	Result	Execution time	Memory
587992		georgievskiy	Aliens (IOI16_aliens)	C++17	41 / 100	2080 ms	125424 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;

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));
    vector<vector<int>> opt(n + 1, vector<int>(k + 2, n));
    for (int j = 0; j <= k; j++)
        d[0][j] = 0, opt[0][j] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = k; j >= 1; j--) {

            for (int f = opt[i - 1][j]; f <= min(i - 1, opt[i][j + 1]); f++) {
                ll c = d[f][j - 1];
                c += sqr(x[i - 1] - y[f] + 1) - t[f];
                if (c < d[i][j])
                    d[i][j] = c, opt[i][j] = f;
            }
        }
    }
    return d.back().back();
}

Compilation message (stderr)

aliens.cpp: In lambda function:
aliens.cpp:13:95: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   13 |     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: 0 / 19
• Subtask 6: 0 / 40