Submission #1057367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057367		TAhmed33	Aliens (IOI16_aliens)	C++98	0 / 100	0 ms	348 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include "grader.cpp"
const ll inf = 1e16;
inline ll sq (ll x) {
    return x * x;
}
ll take_photos (int n, int m, int k, vector <int> r, vector <int> c) {
    array <ll, 2> a[n + 2];
    for (int i = 0; i < n; i++) {
        if (r[i] < c[i]) {
            swap(r[i], c[i]);
        }
        c[i]++; r[i]++;
        a[i + 1] = {c[i], r[i]};
    }
    sort(a + 1, a + n + 1);
    ll dp[n + 2][k + 1] = {};
    ll pre[n + 1][n + 1] = {};
    for (int l = n; l >= 1; l--) {
        pre[l][l] = a[l][1];
        for (int r = l + 1; r <= n; r++) {
            pre[l][r] = max(pre[l][r - 1], a[r][1]);
        }
    }
    a[n + 1] = {m + 1, m + 1};
    for (int i = n; i >= 1; i--) {
        dp[i][0] = inf;
        for (int j = 1; j <= k; j++) {
            dp[i][j] = inf;
            for (int l = i; l <= n; l++) {
                ll x = sq(pre[i][l] - a[i][0] + 1);
                if (pre[i][k] >= a[l + 1][0]) {
                    x -= sq(pre[i][l] - a[l + 1][0] + 1);
                }
                dp[i][j] = min(dp[i][j], x + dp[l + 1][j - 1]);
            }
        }
    }
    return dp[1][k];
}

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