제출 #700983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
700983		rembocoder	Aliens (IOI16_aliens)	C++17	컴파일 에러	0 ms	0 KiB

aliens

#include "aliens.h"

#include<bits/stdc++.h>

using namespace std;

#define int long long

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;
}

int divide_up(int a, int 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<int, int>> segs(n);
    for (int 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<int, int>> new_segs;
    new_segs.push_back({-1, -1});
    int 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<int>> a(k + 1, vector<int>(n));
    vector<int> b(n);
    for (int i = 0; i < n - 1; i++) {
        b[i] = -2 * segs[i + 1].first;
    }

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

    auto count_a = [&](int j, int 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<int, int>>> ch(k + 1);
    vector<int> last(k + 1);
    dp[0][0] = 0;
    count_a(0, 0);
    ch[0].push_back({-1, 0});
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= i && j <= k; j++) {
            // dp[j][i]
            int 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]++;
            }
            int 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;
                int ind = ch[j].back().second;
                if (a[j][ind] + b[ind] * x < a[j][i] + b[i] * x) {
                    break;
                }
                ch[j].pop_back();
            }
            int 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], int(ch[j].size() - 1));
        }
    }
    int ans = 2e18;
    for (int j = 1; j <= k; j++) {
        ans = min(ans, dp[j][n - 1]);
    }
    return ans;
}

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

aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:73: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]
   73 |             while (last[j - 1] + 1 < ch[j - 1].size() && ch[j - 1][last[j - 1] + 1].first <= x) {
aliens.cpp:7:13: error: expected primary-expression before 'long'
    7 | #define int long long
      |             ^~~~
aliens.cpp:99:36: note: in expansion of macro 'int'
   99 |             last[j] = min(last[j], int(ch[j].size() - 1));
      |                                    ^~~