제출 #751503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751503		Desh03	Aliens (IOI16_aliens)	C++17	100 / 100	223 ms	6860 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

struct point {
    int x, y;
    bool operator < (const point &p) const {
        return x == p.x ? y < p.y : x < p.x;
    }
};

struct line {
    int m;
    long long c;
    int s;
    long long eval(const int &x) {
        return 1LL * m * x + c;
    }
    bool good(const line &l1, const line &l2) {
        return __int128(l1.c - l2.c) * (l1.m - m) < __int128(c - l1.c) * (l2.m - l1.m);
    }
};

int N;
vector<point> r;
vector<long long> dp;
vector<int> cnt;

struct CHT {
    deque<line> hull;
    void insert(line l) {
        while (hull.size() > 1 && !l.good(hull.back(), *next(hull.rbegin()))) hull.pop_back();
        hull.push_back(l);
    }
    pair<long long, int> qry(int x) {
        while (hull.size() > 1 && hull[0].eval(x) > hull[1].eval(x)) hull.pop_front();
        return {hull[0].eval(x), hull[0].s};
    }
};

long long sq(int x) {
    return 1LL * x * x;
}

void aliens(long long lambda) {
   CHT cht;
   cht.insert({-2 * r[0].x, sq(r[0].x) - 2 * r[0].x, 0});
   for (int i = 0; i < N; i++) {
        auto [mn, cnt_] = cht.qry(r[i].y);
        dp[i] = mn + sq(r[i].y + 1) + lambda;
        cnt[i] = cnt_ + 1;
        if (i < N - 1) {
            cht.insert({-2 * r[i + 1].x, dp[i] + sq(r[i + 1].x) - 2 * r[i + 1].x - sq(max(0, r[i].y - r[i + 1].x + 1)), cnt[i]});
        }
   }
}

long long take_photos(int n, int m, int k, vector<int> R, vector<int> C) {
    vector<point> f;
    r = vector<point> ();
    for (int i = 0; i < n; i++) {
        if (R[i] > C[i]) swap(R[i], C[i]);
        f.push_back({R[i], C[i]});
    }
    sort(f.begin(), f.end());
    r.push_back(f[0]);
    for (int i = 1; i < n; i++) {
        if (r.back().x == f[i].x) {
            r.pop_back();
            r.push_back(f[i]);
        } else if (f[i].y > r.back().y) {
            r.push_back(f[i]);
        }
    }
    N = r.size(), k = min(N, k);
    dp = vector<long long> (N), cnt = vector<int> (N);
    long long l_ = 0, r_ = INF;
    while (l_ < r_) {
        long long m_ = l_ + r_ >> 1;
        aliens(m_);
        if (cnt[N - 1] > k) l_ = m_ + 1;
        else r_ = m_ ;
    }
    aliens(l_);
    return dp[N - 1] - l_ * k;
}

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:81:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         long long m_ = l_ + r_ >> 1;
      |                        ~~~^~~~

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