Submission #725068

#	Time	Username	Problem	Language	Result	Execution time	Memory
725068		rembocoder	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	232 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

bool comp_points(const pair<long long, long long>& a, const pair<long long, long long>& b) {
    if (a.first != b.first) {
        return a.first < b.first;
    }
    return a.second > b.second;
}

long long div_up(long long a, long long b) {
    if (b < 0) {
        a = -a;
        b = -b;
    }
    if (a < 0) {
        return a / b;
    }
    return (a + b - 1) / b;
}

long long take_photos(int n, int m, int k, vector<int> points_x, vector<int> points_y) {
    vector<pair<long long, long long>> points;
    for (int i = 0; i < n; i++) {
        if (points_x[i] > points_y[i]) {
            swap(points_x[i], points_y[i]);
        }
        points.push_back({points_x[i], points_y[i]});
    }
    sort(points.begin(), points.end(), comp_points);
    vector<pair<long long, long long>> points_fin;
    points_fin.push_back({-1, -1});
    long long cur_largest_y = -2e9;
    for (int i = 0; i < n; i++) {
        if (points[i].second <= cur_largest_y) {
            continue;
        }
        cur_largest_y = points[i].second;
        points_fin.push_back(points[i]);
    }
    points = points_fin;
    n = points.size();
    vector<long long> b(n);
    for (int i = 0; i < n - 1; i++) {
        b[i] = 2 * points[i + 1].first;
    }
    vector<long long> dp(n, 2e12);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        cout << points[i].first << ' ' << points[i].second << endl;
    }
    long long ans = 2e12;
    for (int p = 0; p < k; p++) {
        vector<long long> new_dp(n, 2e12);
        vector<long long> a(n);
        for (int i = 0; i < n - 1; i++) {
            a[i] = dp[i] + points[i + 1].first * points[i + 1].first -
                                        max(0ll, points[i].second - points[i + 1].first + 1) *
                                        max(0ll, points[i].second - points[i + 1].first + 1);
        }
        vector<pair<long long, long long>> ch;
        ch.push_back({-4e12 - 10, p});
        for (int i = p + 1; i < n; i++) {
            int j = ch[upper_bound(ch.begin(), ch.end(), make_pair(points[i].second + 1, (long long)(2e18))) - ch.begin() - 1].second;
            new_dp[i] = (points[i].second + 1) * (points[i].second + 1) + a[j] - b[j] * (points[i].second + 1);
            if (i == n - 1) {
                continue;
            }
            while (true) {
                long long x = ch.back().first;
                int j = ch.back().second;
                if (a[j] - b[j] * x < a[i] - b[i] * x) {
                    break;
                }
                ch.pop_back();
            }
            j = ch.back().second;
            long long x = div_up(a[i] - a[j], b[i] - b[j]);
            ch.push_back({x, i});
        }
        dp = new_dp;
        ans = min(ans, dp.back());
    }
    return ans;
}

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