Submission #1176089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176089		MisterReaper	Sightseeing in Kyoto (JOI22_kyoto)	C++20	100 / 100	245 ms	17588 KiB

kyoto

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

struct S {
    i64 a, b;
    bool operator< (const S rhs) const {
        return a * rhs.b < b * rhs.a;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int H, W;
    std::cin >> H >> W;
    std::vector<int> A(H), B(W);
    for (int i = 0; i < H; ++i) {
        std::cin >> A[i];
    }
    for (int i = 0; i < W; ++i) {
        std::cin >> B[i];
    }

    std::set<int> a, b;
    for (int i = 0; i < H; ++i) {
        a.emplace(i);
    }
    for (int i = 0; i < W; ++i) {
        b.emplace(i);
    }

    using TP = std::tuple<S, int, int>;
    std::priority_queue<TP, std::vector<TP>, std::greater<>> pqa;
    std::priority_queue<TP, std::vector<TP>, std::greater<>> pqb;
    for (int i = 0; i < H - 1; ++i) {
        pqa.emplace(S{A[i] - A[i + 1], 1}, i, i + 1);
    }
    for (int i = 0; i < W - 1; ++i) {
        pqb.emplace(S{B[i] - B[i + 1], 1}, i, i + 1);
    }

    pqa.emplace(S{i64(1E10), 1}, -1, -1);
    pqb.emplace(S{i64(1E10), 1}, -1, -1);

    i64 ans = 0;
    while (pqa.size() + pqb.size() > 2) {
        if (pqa.top() < pqb.top()) {
            auto[_, i, j] = pqa.top();
            pqa.pop();
            if (!a.contains(i) || !a.contains(j)) {
                continue;
            }
            auto it = a.lower_bound(j);
            int r = -1;
            if (it != --a.end()) {
                r = *std::next(it);
            }
            a.erase(it);
            if (r == -1) {
                debug(B[*b.rbegin()], j - i);
                ans += 1LL * B[*b.rbegin()] * (j - i);
            } else {
                pqa.emplace(S{A[i] - A[r], r - i}, i, r);
            }
        } else {
            auto[_, i, j] = pqb.top();
            pqb.pop();
            if (!b.contains(i) || !b.contains(j)) {
                continue;
            }
            auto it = b.lower_bound(j);
            int r = -1;
            if (it != --b.end()) {
                r = *std::next(it);
            }
            b.erase(it);
            if (r == -1) {
                debug(A[*a.rbegin()], j - i);
                ans += 1LL * A[*a.rbegin()] * (j - i);
            } else {
                pqb.emplace(S{B[i] - B[r], r - i}, i, r);
            }
        }
    }

    std::cout << ans << '\n';

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60