QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#337703#1880. Nikanor Loves GamesjrjyyRE 0ms0kbC++141.7kb2024-02-25 13:06:562024-02-25 13:06:57

Judging History

你现在查看的是最新测评结果

  • [2024-02-25 13:06:57]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-02-25 13:06:56]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using i128 = __int128_t;
using P = std::complex<i64>;
i128 cross(const P &x, const P &y) {
    return i128(x.real()) * y.imag() - i128(y.real()) * x.imag();
}

int main() {
    freopen("gamble.in", "r", stdin);
    freopen("gamble.out", "w", stdout);
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;

    std::vector<int> a(n), b(n), w(n), v{1};
    i64 sum = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i] >> b[i] >> w[i];
        v.push_back(a[i]);
        v.push_back(b[i]);
        sum += w[i];
        w[i] *= 2;
    }

    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    const int m = int(v.size());

    std::vector<i64> f(m);
    for (int i = 0; i < n; ++i) {
        f[std::lower_bound(v.begin(), v.end(), a[i]) - v.begin()] += w[i];
        f[std::lower_bound(v.begin(), v.end(), b[i]) - v.begin()] += w[i];
    }
    std::partial_sum(f.begin(), f.end(), f.begin());

    std::vector<P> stk;
    for (int i = 0; i < m; ++i) {
        P p(4ll * v[i], f[i]);
        while (stk.size() > 1 && cross(stk.back() - stk.end()[-2], p - stk.back()) >= 0) {
            stk.pop_back();
        }
        stk.push_back(p);
    }

    auto query = [&](int k) {
        auto eval = [&](const P &p) {
            return p.imag() - k * p.real();
        };
        while (stk.size() > 1 && eval(stk.back()) <= eval(stk.end()[-2])) {
            stk.pop_back();
        }
        return eval(stk.back());
    };

    i64 ans = -1e18;
    for (int i = 0; i < m; ++i) {
        ans = std::max(ans, f[i] + query(v[i]));
    }
    std::cout << ans / 4.0 - sum << "\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

2
1 4 15
3 5 10

output:


result: