Submission #725070

#	Time	Username	Problem	Language	Result	Execution time	Memory
725070		rembocoder	Aliens (IOI16_aliens)	C++17	60 / 100	2065 ms	11572 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;
    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});
        int entry = 0;
        for (int i = p + 1; i < n; i++) {
            while (entry + 1 < ch.size() && ch[entry + 1].first <= points[i].second + 1) {
                entry++;
            }
            int j = ch[entry].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});
            entry = min(entry, int(ch.size()) - 1);
        }
        dp = new_dp;
        ans = min(ans, dp.back());
    }
    return ans;
}

Compilation message (stderr)

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

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