제출 #731006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
731006		rembocoder	Aliens (IOI16_aliens)	C++17	60 / 100	2072 ms	12788 KiB

aliens

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

using namespace std;

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 divide_up(long long a, long long b) {
    if (b < 0) {
        a = -a;
        b = -b;
    }
    if (a < 0) {
        return a / b;
    } else {
        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<int, int>> points(n);
    for (int i = 0; i < n; i++) {
        if (points_x[i] > points_y[i]) {
            swap(points_x[i], points_y[i]);
        }
        points[i] = {points_x[i], points_y[i] + 1};
    }
    sort(points.begin(), points.end(), cmp);
    vector<pair<int, int>> points_fin;
    points_fin.push_back({-1, -1});
    int max_y = -1;
    for (int i = 0; i < n; i++) {
        if (max_y < points[i].second) {
            max_y = points[i].second;
            points_fin.push_back(points[i]);
        }
    }
    points = points_fin;
    points_fin.clear();
    n = points.size();
    vector<long long> l(n), r(n);
    for (int i = 0; i < n; i++) {
        l[i] = points[i].first;
        r[i] = points[i].second;
    }
    vector<long long> b(n);
    for (int i = 0; i < n - 1; i++) {
        b[i] = 2 * l[i + 1];
    }
    k = min(k, n - 1);
    vector<long long> dp(n, 2e12);
    dp[0] = 0;
    for (int p = 0; p < k; p++) {
        vector<long long> a(n);
        for (int i = 0; i < n - 1; i++) {
            a[i] = dp[i] + l[i + 1] * l[i + 1] - max(0ll, r[i] - l[i + 1]) *
                                                 max(0ll, r[i] - l[i + 1]);
        }
        vector<pair<long long, int>> ch; // {x, ind} – начиная с такого r[i] лучше всего переходить из ind
        ch.push_back({-1, p});
        int cur = 0;
        vector<long long> new_dp(n, 2e12);
        for (int i = p + 1; i < n; i++) {
            while (cur + 1 < ch.size() && ch[cur + 1].first <= r[i]) {
                cur++;
            }
            int j = ch[cur].second;
            new_dp[i] = r[i] * r[i] + a[j] - b[j] * r[i];

            if (i == n - 1) {
                continue;
            }

            while (ch.size()) {
                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();
            }
            if (ch.empty()) {
                ch.push_back({-1, i});
            } else {
                int j = ch.back().second;
                ch.push_back({max(divide_up(a[i] - a[j], b[i] - b[j]), -1ll), i});
            }
            cur = min(cur, int(ch.size()) - 1);
        }
        dp = new_dp;
    }

    return dp.back();
}


// dp[p][i] = min_j( dp[p - 1][j] + (r[i] - l[j + 1])^2 - max(0, r[j] - l[j + 1])^2 )
// dp[p][i] = r[i]^2 + min_j( dp[p - 1][j] + l[j + 1]^2 - max(0, r[j] - l[j + 1])^2 - 2 l[j + 1] r[i] )

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:69:28: 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 + 1 < ch.size() && ch[cur + 1].first <= r[i]) {
      |                    ~~~~~~~~^~~~~~~~~~~

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