Submission #1222345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222345		just	Aliens (IOI16_aliens)	C++20	25 / 100	2096 ms	32272 KiB

aliens

#include "aliens.h"

#include "bits/stdc++.h"
using namespace std;

#define int long long
template<typename T>
using vec = vector<T>;

using pii = pair<int, int>;

#define all(x) x.begin(), x.end()

int sq(int x) { return x * x; }

vec<pii> a;

#define L first
#define R second

const int STEP = 2;

int memo[4000][4000] = {0};
bool done[4000][4000] = {false};
int calc(int i, int k) {
    if (k == 0) return INT_MAX;
    if (k == 1) return sq(abs(a[0].L - a[i].R) + STEP);
    
    if (done[i][k]) return memo[i][k];
    done[i][k] = true;
    
    int ans = sq(abs(a[0].L - a[i].R) + STEP);
    for (int j = 1; j <= i; j++) {
        int overlap = 0;
        if (a[j - 1].R >= a[j].L) overlap = sq(abs(a[j - 1].R - a[j].L) + STEP);
        ans = min(ans, calc(j - 1, k - 1) + sq(abs(a[j].L - a[i].R) + STEP) - overlap);
    }
    
    return memo[i][k] = ans;
}

int take_photos(signed n, signed m, signed k, vec<signed> r, vec<signed> c) {
    a.resize(n);
    
    for (int i = 0; i < n; i++) {
        if (r[i] > c[i]) swap(r[i], c[i]);
        a[i] = {r[i] * STEP, c[i] * STEP};
    }
    
    sort(all(a));
    
    vec<bool> del(n, false);
    int mx = -1;
    for (int i = 0; i < n; i++) {
        auto [l, r] = a[i];
        if (r <= mx) del[i] = true;
        mx = max(mx, r);
    }
    
    vec<pii> tmp; tmp.reserve(n);
    for (int i = 0; i < n; i++) {
        if (!del[i]) tmp.push_back(a[i]);
    }
    
    a = tmp;
    n = a.size();
    
    return calc(n - 1, min(n, k)) / (STEP * STEP);
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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