Submission #700987

#	Time	Username	Problem	Language	Result	Execution time	Memory
700987		rembocoder	Aliens (IOI16_aliens)	C++17	60 / 100	1896 ms	1048576 KiB

aliens

#include "aliens.h"

#include<bits/stdc++.h>

using namespace std;

bool cmp(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 divide_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(int32_t n, int32_t m, int32_t k, vector<int32_t> points_x, vector<int32_t> points_y) {
    vector<pair<long long, long long>> segs(n);
    for (long long i = 0; i < n; i++) {
        segs[i] = {min(points_x[i], points_y[i]), max(points_x[i], points_y[i])};
    }
    sort(segs.begin(), segs.end(), cmp);
    vector<pair<long long, long long>> new_segs;
    new_segs.push_back({-1, -1});
    long long largest_r = -2e18;
    for (auto [l, r]: segs) {
        if (r <= largest_r) {
            continue;
        }
        largest_r = r;
        new_segs.push_back({l, r});
    }
    segs = new_segs;
    n = segs.size();
    new_segs.clear();

    vector<vector<long long>> a(k + 1, vector<long long>(n));
    vector<long long> b(n);
    for (long long i = 0; i < n - 1; i++) {
        b[i] = -2 * segs[i + 1].first;
    }

    vector<vector<long long>> dp(k + 1, vector<long long>(n, 2e18));

    auto count_a = [&](long long j, long long i) {
        if (i == n - 1) {
            return;
        }
        a[j][i] = dp[j][i] + (segs[i + 1].first - 1) * (segs[i + 1].first - 1)
                - max(0ll, segs[i].second - segs[i + 1].first + 1) *
                  max(0ll, segs[i].second - segs[i + 1].first + 1);
    };

    vector<vector<pair<long long, long long>>> ch(k + 1);
    vector<long long> last(k + 1);
    dp[0][0] = 0;
    count_a(0, 0);
    ch[0].push_back({-1, 0});
    for (long long i = 1; i < n; i++) {
        for (long long j = 1; j <= i && j <= k; j++) {
            // dp[j][i]
            long long x = segs[i].second;
            while (last[j - 1] + 1 < ch[j - 1].size() && ch[j - 1][last[j - 1] + 1].first <= x) {
                last[j - 1]++;
            }
            long long from = ch[j - 1][last[j - 1]].second;
            dp[j][i] = segs[i].second * segs[i].second + 2 * segs[i].second + a[j - 1][from] + b[from] * x;
            //cerr << x << ' ' << from << endl;
            //cerr << segs[i].second * segs[i].second - 2 * segs[i].second << ' ' << a[j - 1][from] << ' ' << << endl;
            count_a(j, i);
            if (i == n - 1) {
                continue;
            }
            if (ch[j].empty()) {
                ch[j].push_back({-1, i});
                continue;
            }
            while (true) {
                x = ch[j].back().first;
                long long ind = ch[j].back().second;
                if (a[j][ind] + b[ind] * x < a[j][i] + b[i] * x) {
                    break;
                }
                ch[j].pop_back();
            }
            long long ind = ch[j].back().second;
            x = divide_up(a[j][i] - a[j][ind], b[ind] - b[i]);
            ch[j].push_back({x, i});
            last[j] = min(last[j], (long long)(ch[j].size() - 1));
        }
    }
    long long ans = 2e18;
    for (long long j = 1; j <= k; j++) {
        ans = min(ans, dp[j][n - 1]);
    }
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:71:36: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             while (last[j - 1] + 1 < ch[j - 1].size() && ch[j - 1][last[j - 1] + 1].first <= x) {

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