結果
問題 | No.974 最後の日までに |
ユーザー |
![]() |
提出日時 | 2020-06-11 00:31:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,230 bytes |
コンパイル時間 | 879 ms |
コンパイル使用メモリ | 93,888 KB |
実行使用メモリ | 28,160 KB |
最終ジャッジ日時 | 2024-06-23 20:45:01 |
合計ジャッジ時間 | 8,828 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 WA * 8 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;int W;int M;ll a[52], b[52], c[52];map<ll, ll> mpl, mpr;vector<int> buf;bool left_half;void dfs(int c1, int c2){if(c1 == 0 && c2 == 0){int cur = (left_half ? 0 : M);ll money = 0, likes = 0;for(int i : buf) {if(i == 1){money += a[cur];}else{likes += b[cur+1];money -= c[cur+1];}cur += i;}if(left_half) {if(mpl.count(money) > 0){mpl[money] = max(mpl[money], likes);}else{mpl[money] = likes;}}else{if(mpr.count(money) > 0){mpr[money] = max(mpr[money], likes);}else{mpr[money] = likes;}}}if(c1 != 0){buf.push_back(1);dfs(c1-1, c2);buf.pop_back();}if(c2 != 0){buf.push_back(2);dfs(c1, c2-1);buf.pop_back();}}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;cin >> W;for(int i = 0; i < W; i++) cin >> a[i] >> b[i] >> c[i];if(W == 1){cout << 0 << endl;return 0;}M = W/2;left_half = true;for(int i = 0; 2*i <= M; i++){dfs(M-2*i, i);}left_half = false;for(int i = 0; 2*i <= W-M; i++){dfs(W-M-2*i, i);}auto p = mpr.end();ll cur_max = 0;while(true){p--;cur_max = max(cur_max, p->second);mpr[p->first] = cur_max;if(p == mpr.begin()) break;}ll ans = 0;// for(auto i : mpl) cout << i.first << ':' << i.second << ' ';// cout << endl;// for(auto i : mpr) cout << i.first << ':' << i.second << ' ';// cout << endl;for(auto i : mpl){ll money = i.first;ll likes = i.second;auto p = mpr.lower_bound(-money);if(p == mpr.end()) continue;ans = max(ans, likes+p->second);}cout << ans << endl;}