結果
問題 | No.974 最後の日までに |
ユーザー | chocorusk |
提出日時 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 637 ms
16,656 KB |
testcase_01 | AC | 628 ms
16,788 KB |
testcase_02 | AC | 626 ms
16,656 KB |
testcase_03 | AC | 621 ms
16,788 KB |
testcase_04 | AC | 630 ms
16,660 KB |
testcase_05 | AC | 629 ms
16,784 KB |
testcase_06 | AC | 628 ms
16,660 KB |
testcase_07 | AC | 624 ms
16,784 KB |
testcase_08 | AC | 622 ms
16,792 KB |
testcase_09 | AC | 628 ms
16,788 KB |
testcase_10 | AC | 638 ms
16,792 KB |
testcase_11 | AC | 649 ms
16,912 KB |
testcase_12 | AC | 629 ms
16,660 KB |
testcase_13 | AC | 625 ms
16,792 KB |
testcase_14 | AC | 635 ms
16,664 KB |
testcase_15 | AC | 624 ms
16,660 KB |
testcase_16 | AC | 621 ms
16,660 KB |
testcase_17 | AC | 624 ms
16,660 KB |
testcase_18 | AC | 623 ms
16,788 KB |
testcase_19 | AC | 637 ms
16,664 KB |
testcase_20 | AC | 624 ms
16,788 KB |
testcase_21 | AC | 629 ms
16,920 KB |
testcase_22 | AC | 625 ms
16,792 KB |
testcase_23 | AC | 630 ms
16,660 KB |
testcase_24 | AC | 625 ms
16,788 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 506 ms
13,868 KB |
testcase_28 | AC | 636 ms
16,792 KB |
testcase_29 | AC | 2 ms
5,248 KB |
testcase_30 | AC | 639 ms
16,788 KB |
testcase_31 | AC | 2 ms
5,248 KB |
testcase_32 | AC | 2 ms
5,248 KB |
testcase_33 | AC | 330 ms
11,564 KB |
testcase_34 | AC | 628 ms
16,788 KB |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | AC | 2 ms
5,248 KB |
testcase_37 | AC | 636 ms
16,656 KB |
testcase_38 | AC | 1 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
testcase_40 | AC | 479 ms
13,996 KB |
testcase_41 | AC | 622 ms
16,580 KB |
testcase_42 | AC | 643 ms
16,664 KB |
testcase_43 | AC | 635 ms
16,664 KB |
testcase_44 | AC | 537 ms
13,992 KB |
testcase_45 | AC | 329 ms
11,568 KB |
testcase_46 | AC | 2 ms
5,248 KB |
testcase_47 | AC | 2 ms
5,248 KB |
testcase_48 | AC | 2 ms
5,248 KB |
testcase_49 | AC | 2 ms
5,248 KB |
testcase_50 | AC | 2 ms
5,248 KB |
testcase_51 | AC | 2 ms
5,248 KB |
ソースコード
#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_popcountusing 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;}