結果
問題 | No.974 最後の日までに |
ユーザー |
![]() |
提出日時 | 2019-12-06 22:43:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 563 ms / 2,000 ms |
コード長 | 2,107 bytes |
コンパイル時間 | 1,832 ms |
コンパイル使用メモリ | 180,908 KB |
実行使用メモリ | 43,392 KB |
最終ジャッジ日時 | 2024-10-04 01:20:54 |
合計ジャッジ時間 | 14,215 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 49 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 10000000000000000 map<long long,long long> mp1,mp2,mp3,mp4; void dfs1(vector<long long> &a,vector<long long> &b,vector<long long> &c,int ind,long long love,long long money){ int n = a.size(); if(ind==n){ mp1[money] = max(mp1[money],love); return; } else if(ind==n+1){ mp2[money] = max(mp2[money],love); return; } dfs1(a,b,c,ind+1,love,money+a[ind]); if(ind!=n-1)dfs1(a,b,c,ind+2,love+b[ind+1],money-c[ind+1]); else dfs1(a,b,c,ind+2,love,money); } void dfs2(vector<long long> &a,vector<long long> &b,vector<long long> &c,int ind,long long love,long long money,bool f){ int n = a.size(); if(ind==n){ if(f)mp3[money] = max(mp3[money],love); else mp4[money] = max(mp4[money],love); return; } else if(ind==n+1){ return; } dfs2(a,b,c,ind+1,love,money+a[ind],f); if(ind!=n-1)dfs2(a,b,c,ind+2,love+b[ind+1],money-c[ind+1],f); else dfs2(a,b,c,ind+2,love,money,f); } int main(){ int D; cin>>D; vector<long long> a(D),b(D),c(D); for(int i=0;i<D;i++){ cin>>a[i]>>b[i]>>c[i]; } vector<long long> a1,a2,b1,b2,c1,c2; for(int i=0;i<D;i++){ if(i<D/2){ a1.push_back(a[i]); b1.push_back(b[i]); c1.push_back(c[i]); } else{ a2.push_back(a[i]); b2.push_back(b[i]); c2.push_back(c[i]); } } dfs1(a1,b1,c1,0,0,0); dfs2(a2,b2,c2,0,0,0,true); if(b2.size()!=0)dfs2(a2,b2,c2,1,b2.front(),-c2.front(),false); long long last = 0; for(auto it = mp3.rbegin();it!=mp3.rend();it++){ (*it).second = max((*it).second,last); last = (*it).second; } last=0; for(auto it = mp4.rbegin();it!=mp4.rend();it++){ (*it).second = max((*it).second,last); last = (*it).second; } long long ans = 0; for(auto x:mp1){ auto it = mp3.lower_bound(-x.first); if(it==mp3.end())continue; ans = max(ans,x.second + (*it).second); } for(auto x:mp2){ auto it = mp4.lower_bound(-x.first); if(it==mp4.end())continue; ans = max(ans,x.second + (*it).second); } cout<<ans<<endl; return 0; }