結果
問題 |
No.1014 competitive fighting
|
ユーザー |
|
提出日時 | 2020-05-02 02:43:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,080 bytes |
コンパイル時間 | 1,373 ms |
コンパイル使用メモリ | 97,880 KB |
最終ジャッジ日時 | 2025-01-10 05:44:45 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 WA * 1 TLE * 18 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <functional> using lint = long long; constexpr lint INF = 1LL << 60; struct Item { lint a, b, c; int id; }; void solve() { int n; std::cin >> n; std::vector<Item> ts(n); for (int i = 0; i < n; ++i) { auto& t = ts[i]; std::cin >> t.a >> t.b >> t.c; t.id = i; } std::sort(ts.begin(), ts.end(), [](auto lhs, auto rhs) { return lhs.a < rhs.a; }); std::vector<lint> ans(n, -1), acc(n, -1); std::function<lint(int)> dfs = [&](int v) -> lint { if (ans[v] != -1) { if (v > 0 && acc[v - 1] != -1) { acc[v] = std::max(ans[v], acc[v - 1]); } return ans[v]; } int ok = -1, ng = n; while (ng - ok > 1) { int mid = (ok + ng) / 2; if (ts[mid].a <= ts[v].b - ts[v].c) { ok = mid; } else { ng = mid; } } if (ok == -1) { ans[v] = ts[v].b; return ans[v]; } lint res = 0; ans[v] = INF; for (int u = ok; u >= 0; --u) { if (u == v) continue; if (acc[u] != -1) { res = std::max(res, acc[u] + ts[v].b); break; } else { res = std::max(res, dfs(u) + ts[v].b); } } if (res >= INF) res = INF; ans[v] = res; if (v == 0) { acc[v] = ans[v]; } else if (acc[v - 1] != -1) { acc[v] = std::max(ans[v], acc[v - 1]); } return ans[v]; }; std::vector<lint> as(n); for (int v = 0; v < n; ++v) as[ts[v].id] = dfs(v); for (auto a : as) { if (a == INF) { std::cout << "BAN" << std::endl; } else { std::cout << a << std::endl; } } } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }