제출 #585993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585993		georgievskiy	Aliens (IOI16_aliens)	C++17	12 / 100	69 ms	4312 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];
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()/*, [](pii a, pii b) {return a.first < b.first || a.first == b.first && a.second > b.second;}*/);
    vector<pii> st;
    int mx = -1;
    for (pii p : a) {
        //if (p.second == mx)
        //    st.pop_back();
        if (p.second >= mx)
            st.push_back(p), mx = p.second;
    }
    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 j = 0; j <= i; j++) {
            ll c = sqr(x[i] + 1) - 2 * (x[i] + 1) * y[j] + t[j];
            for (int w = 1; w <= k; w++) {
                int prev = 0;
                if (j)
                    prev = d[j - 1][w - 1];
                d[i][w] = min(d[i][w], prev + c);
            }
        }
    }

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

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