結果
問題 | No.974 最後の日までに |
ユーザー |
![]() |
提出日時 | 2020-06-11 00:41:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 700 ms / 2,000 ms |
コード長 | 2,690 bytes |
コンパイル時間 | 1,090 ms |
コンパイル使用メモリ | 94,512 KB |
実行使用メモリ | 30,976 KB |
最終ジャッジ日時 | 2024-06-23 20:56:19 |
合計ジャッジ時間 | 16,839 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#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){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);}// 境目でデートするM++;mpl.clear(); mpr.clear();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);}p = mpr.end();cur_max = 0;while(true){p--;cur_max = max(cur_max, p->second);mpr[p->first] = cur_max;if(p == mpr.begin()) break;}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;}