結果
問題 | No.974 最後の日までに |
ユーザー |
![]() |
提出日時 | 2020-01-17 23:18:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 649 ms / 2,000 ms |
コード長 | 2,223 bytes |
コンパイル時間 | 1,197 ms |
コンパイル使用メモリ | 119,576 KB |
実行使用メモリ | 16,920 KB |
最終ジャッジ日時 | 2024-10-04 01:31:53 |
合計ジャッジ時間 | 25,156 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<ll, ll> P; int main() { int w; cin>>w; ll a[55], b[55], c[55], x[55]; ll sa=0; for(int i=0; i<w; i++){ cin>>a[i]>>b[i]>>c[i]; sa+=a[i]; } for(int i=1; i<w; i++){ x[i]=a[i]+a[i-1]+c[i]; } if(w<=2){ cout<<0<<endl; return 0; } vector<P> v1, v2, v11, v22; for(int i=0; i<(1<<(w/2)); i+=2){ bool dame=0; for(int j=1; j<w/2; j++){ if((i&(1<<j))!=0 && (i&(1<<(j-1)))!=0){ dame=1; break; } } if(dame) continue; ll xs=0, bs=0; for(int j=1; j<w/2; j++){ if(i&(1<<j)){ xs+=x[j], bs+=b[j]; } } v1.push_back({xs, bs}); if((i&(1<<(w/2-1)))==0) v11.push_back({xs, bs}); } for(int i=0; i<(1<<(w-w/2)); i+=2){ bool dame=0; for(int j=1; j<w-w/2; j++){ if((i&(1<<j))!=0 && (i&(1<<(j-1)))!=0){ dame=1; break; } } if(dame) continue; ll xs=0, bs=0; for(int j=1; j<w-w/2; j++){ if(i&(1<<j)){ xs+=x[w/2+j], bs+=b[w/2+j]; } } v2.push_back({xs, bs}); if(!(i&2)) v22.push_back({xs, bs}); } sort(v1.begin(), v1.end()); sort(v11.begin(), v11.end()); sort(v2.begin(), v2.end()); sort(v22.begin(), v22.end()); for(int i=1; i<v2.size(); i++){ v2[i].second=max(v2[i].second, v2[i-1].second); } for(int i=1; i<v22.size(); i++){ v22[i].second=max(v22[i].second, v22[i-1].second); } ll ans=0; for(auto p:v1){ if(p.first>sa) continue; int k=upper_bound(v2.begin(), v2.end(), P(sa-p.first, 1e18))-v2.begin(); if(k==0) continue; ans=max(ans, p.second+v2[k-1].second); } for(auto p:v11){ if(p.first>sa-x[w/2]) continue; int k=upper_bound(v22.begin(), v22.end(), P(sa-p.first-x[w/2], 1e18))-v22.begin(); if(k==0) continue; ans=max(ans, p.second+v22[k-1].second+b[w/2]); } cout<<ans<<endl; return 0; }