Submission #869176

#	Time	Username	Problem	Language	Result	Execution time	Memory
869176		rembocoder	Aliens (IOI16_aliens)	C++17	60 / 100	2056 ms	12944 KiB

aliens

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

using namespace std;

const long long inf = 2e18;

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

long long sqr(long long a) {
    return a * a;
}

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

long long take_photos(int n, int m, int k, vector<int> x, vector<int> y) {
    vector<pair<int, int>> points;
    for (int i = 0; i < n; i++) {
        if (x[i] > y[i]) {
            swap(x[i], y[i]);
        }
        points.push_back({x[i], y[i]});
    }
    points.push_back({-1, -1});
    n++;
    sort(points.begin(), points.end(), cmp);
    vector<pair<int, int>> new_points;
    int max_y = -2;
    for (int i = 0; i < n; i++) {
        if (points[i].second <= max_y) {
            continue;
        }
        max_y = points[i].second;
        new_points.push_back(points[i]);
    }
    n = new_points.size();
    k = min(n - 1, k);
    vector<long long> l(n), r(n);
    for (int i = 0; i < n; i++) {
        l[i] = new_points[i].first;
        r[i] = new_points[i].second + 1;
    }
    vector<long long> dp(n, inf);
    dp[0] = 0;
    for (int p = 0; p < k; p++) {
        vector<long long> a(n - 1), b(n - 1);
        for (int i = 0; i < n - 1; i++) {
            a[i] = dp[i] + sqr(l[i + 1]) - sqr(max(0ll, r[i] - l[i + 1]));
            b[i] = 2 * l[i + 1];
        }
        vector<pair<long long, int>> ch(1, {0ll, p});
        vector<long long> new_dp(n, inf);
        int cur_entry = 0;
        for (int i = p + 1; i < n; i++) {
            while (cur_entry + 1 < ch.size() && ch[cur_entry + 1].first <= r[i]) {
                cur_entry++;
            }
            int j = ch[cur_entry].second;
            new_dp[i] = sqr(r[i]) + a[j] - b[j] * r[i];
            if (i == n - 1 || p == 0) {
                continue;
            }
            while (!ch.empty()) {
                int j = ch.back().second;
                long long x = ch.back().first;
                if (a[i] - b[i] * x <= a[j] - b[j] * x) {
                    ch.pop_back();
                } else {
                    break;
                }
            }
            if (ch.empty()) {
                ch.push_back({0ll, i});
            } else {
                int j = ch.back().second;
                long long x = div_up(a[i] - a[j], b[i] - b[j]);
                ch.push_back({x, i});
            }
            if (cur_entry >= ch.size()) {
                cur_entry = ch.size() - 1;
            }
        }
        dp = new_dp;
    }
    return dp.back();
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:69:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             while (cur_entry + 1 < ch.size() && ch[cur_entry + 1].first <= r[i]) {
      |                    ~~~~~~~~~~~~~~^~~~~~~~~~~
aliens.cpp:93:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             if (cur_entry >= ch.size()) {
      |                 ~~~~~~~~~~^~~~~~~~~~~~

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