Submission #393072

#	Time	Username	Problem	Language	Result	Execution time	Memory
393072		Tc14	Aliens (IOI16_aliens)	C++17	25 / 100	2080 ms	22348 KiB

aliens

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const ll LLINF = (ll)1e18 + 10;

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

ll take_photos(int n, int m, int k, ve<int> R, ve<int> C) {

    map<int, int> M;
    ve<pii> P;

    for (int i = 0; i < n; i++) {
        int r = R[i];
        int c = C[i];
        if (c < r) swap(r, c);
        if (M.find(r) == M.end()) M[r] = c;
        else M[r] = max(M[r], c);
    }

    int cOld = -1;
    n = 0;
    for (pii p : M) {
        int r, c;
        tie(r, c) = p;
        if (c > cOld) {
            cOld = c;
            P.push_back({r, c});
            n++;
        }
    }

    ve<ll> L(n);
    for (int i = 1; i < n; i++) {
        if (P[i - 1].second >= P[i].first) {
            L[i] = sq(P[i - 1].second - P[i].first + 1);
        }
    }

    ve<ve<ll>> DP(k + 1, ve<ll>(n));
    for (int i = 0; i < n; i++) {
        DP[1][i] = sq(P[i].second - P[0].first + 1);
    }

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

            DP[i][j] = LLINF;
            for (int l = i - 1; l <= j; l++) {

                ll v = DP[i - 1][l - 1];
                v += sq(P[j].second - P[l].first + 1);
                v -= L[l];

                DP[i][j] = min(DP[i][j], v);
            }
        }
    }

    return DP[min(k, n)][n - 1];
}

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