Submission #1093268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093268		Zicrus	Aliens (IOI16_aliens)	C++17	0 / 100	2097 ms	432 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

int N;
vector<pair<int, int>> points;

long long calc(int a, int b, int largest) {
    long long cost = ((long long) (b - a + 1)) * (b - a + 1);
    if (largest > a) {
        cost -= ((long long) (largest - a + 1)) * (largest - a + 1);
    }
    return cost;
}

long long dp(int i, int largest, int k) {
    if (k == 1) {
        return calc(points[i].first, points[N - 1].second, largest);
    }

    long long best = numeric_limits<long long>::max();
    for (int j = i; j < N - k + 1; j++) {
        best = min(
            best,
            calc(points[i].first, points[j].second, largest) + dp(j + 1, points[j].second, k - 1)
        );
    }

    return best;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector<pair<int, int>> all_points = vector<pair<int, int>>(n);

    for (int i = 0; i < n; i++) {
        int b = min(r[i], c[i]);
        int e = max(r[i], c[i]);
        all_points[i] = make_pair(b, -e);
    }

    sort(all_points.begin(), all_points.end());

    points = vector<pair<int, int>>();

    points.push_back(make_pair(all_points[0].first, -all_points[0].second));
    int largest = -all_points[0].second;

    for (int i = 1; i < n; i++) {
        if (largest >= -all_points[i].second) {
            continue;
        }

        largest = -all_points[i].second;
        points.push_back(make_pair(all_points[i].first, -all_points[i].second));
    }

    N = points.size();

    return dp(0, 0, k > N ? N : 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