結果
問題 | No.974 最後の日までに |
ユーザー |
|
提出日時 | 2024-02-27 19:34:17 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 1,374 bytes |
コンパイル時間 | 1,461 ms |
コンパイル使用メモリ | 112,240 KB |
実行使用メモリ | 13,520 KB |
最終ジャッジ日時 | 2024-09-29 12:08:43 |
合計ジャッジ時間 | 5,841 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;const long long INF = 1LL << 61;int main() {int W;cin >> W;vector<long long> a(W), b(W), c(W);for (int i = 0; i < W; i++) {cin >> a[i] >> b[i] >> c[i];}if (W == 1) {cout << 0 << endl;} else {vector<pair<long long, long long>> A;auto dfs = [&] (auto dfs, int l, int r, long long M, long long L) -> void {if (l == r) {A.push_back(make_pair(M, L));return;}dfs(dfs, l + 1, r, M + a[l], L);if (l + 2 <= r) {dfs(dfs, l + 2, r, M - c[l + 1], L + b[l + 1]);}};long long ans = 0;for (int mid : {W / 2, W / 2 - 1}) {dfs(dfs, 0, mid, 0LL, 0LL);vector<pair<long long, long long>> B = A;int N = B.size();sort(B.rbegin(), B.rend());long long MAXB = -INF;for (int i = 0; i < N; i++) {B[i].second = max(B[i].second, MAXB);MAXB = max(MAXB, B[i].second);}sort(B.begin(), B.end());A.clear();dfs(dfs, mid, W, 0LL, 0LL);B.push_back(make_pair(INF, -INF));N = A.size();for (int i = 0; i < N; i++) {auto itr = lower_bound(B.begin(), B.end(), make_pair(-A[i].first, 0LL));ans = max(ans, itr->second + A[i].second);}A.clear();}cout << ans << endl;}}