Submission #562787

#	Time	Username	Problem	Language	Result	Execution time	Memory
562787		elazarkoren	Aliens (IOI16_aliens)	C++17	25 / 100	2078 ms	12884 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
#define int ll
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 5001;
const ll infinity = 1e18;

ll dp[MAX_N][MAX_N];
int ind[MAX_N];
int prefix_max[MAX_N];

bitset<MAX_N> inside;

long long take_photos(int32_t n, int32_t m, int32_t k, std::vector<int32_t> r, std::vector<int32_t> c) {
    for (int i = 0; i < n; i++) {
        if (r[i] > c[i]) swap(r[i], c[i]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (r[j] < r[i] && c[j] > c[i]) {
                inside[i] = true;
                r[i] = m + 1, c[i] = m + 1;
                break;
            }
        }
    }
    iota(ind, ind + n, 0);
    sort(ind, ind + n, [&] (int i, int j) {
        return r[i] + c[i] < r[j] + c[j];
    });
    n -= inside.count();
    for (int i = 0; i < n; i++) {
        prefix_max[i + 1] = max<ll>(prefix_max[i], c[ind[i]] + 1);
    }
    fill(dp[0], dp[0] + n, infinity);
    for (int j = 1; j <= k; j++) {
        for (int i = 0; i < n; i++) {
            dp[j][i] = infinity;
            int left = m, right = 0;
            for (int l = i; l >= 0; l--) {
                chkmin(left, ll(r[ind[l]]));
                chkmax(right, ll(c[ind[l]] + 1));
                ll x = (l ? dp[j - 1][l - 1] : 0) + ll(right - left) * (right - left);
                if (prefix_max[l] > left) {
                    x -= (prefix_max[l] - left) * (prefix_max[l] - left);
                }
                chkmin(dp[j][i], x);
            }
        }
    }
    return dp[k][n - 1];
}
//6 7 2
//0 3
//4 4
//4 6
//4 5
//4 6
//0 5

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