結果
問題 | No.974 最後の日までに |
ユーザー |
![]() |
提出日時 | 2020-06-16 15:55:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,203 bytes |
コンパイル時間 | 1,955 ms |
コンパイル使用メモリ | 201,808 KB |
最終ジャッジ日時 | 2025-01-11 04:38:39 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 WA * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int64_t INF = INT64_C(1) << 60;template <typename T>bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}int main() {ios::sync_with_stdio(false);cin.tie(0);int W;cin >> W;vector<int64_t> A(W), B(W), C(W);for (int i = 0; i < W; i++) {cin >> A[i] >> B[i] >> C[i];}function<void(int, int, int64_t, int64_t, map<int64_t, int64_t> &)> dfs =[&](int now, int end, int64_t money, int64_t love, map<int64_t, int64_t> &mp) {if (now == end) {chmax(mp[money], love);return;}dfs(now + 1, end, money + A[now], love, mp);if (now + 1 < end) dfs(now + 2, end, money - C[now + 1], love + B[now + 1], mp);};auto solve = [&](int w) {map<int64_t, int64_t> A, B;// B[INF] = -INF;// B[-INF] = -INF;dfs(0, w, 0, 0, A);dfs(w, W, 0, 0, B);int64_t res = 0;for (const auto &[key, value] : A) {auto itr = B.lower_bound(-key);if (itr != B.end()) res = max(res, itr->second + value);}return res;};cout << max(solve(W / 2), solve(W / 2 + 1)) << '\n';return 0;}