結果
問題 |
No.2329 Nafmo、イカサマをする
|
ユーザー |
|
提出日時 | 2023-05-29 16:57:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,367 bytes |
コンパイル時間 | 1,218 ms |
コンパイル使用メモリ | 95,260 KB |
実行使用メモリ | 8,748 KB |
最終ジャッジ日時 | 2024-12-28 09:59:57 |
合計ジャッジ時間 | 2,665 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 WA * 23 |
ソースコード
//TLE #include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<tuple> #include<cmath> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<ll,int> P; typedef pair<int,P> PP; const ll MOD=998244353; int main(){ int N,M,K; cin>>N>>M>>K; vector<int> A(N); for(int i=0;i<N;i++){ cin>>A[i]; } A.push_back(0); auto dfs=[&](auto f,int idx, int n)->vector<ll>{ if(idx==n){ return vector<ll>{0}; } vector<ll> tmp=f(f,idx+1,n); set<ll> tmpst; //被りがでないように for(ll v:tmp){ for(ll a:A){ tmpst.insert(v); if(v+a<=M){ tmpst.insert(v+a); } } } vector<ll> res; for(ll v:tmpst){ res.push_back(v); //res.insert(v); } return res; }; vector<ll> res1=dfs(dfs,0,K/2); vector<ll> res2=dfs(dfs,0,K-K/2); ll ans=0; for(ll v:res1){ if(v+res2.back()<=M){ ans=max(ans,res2.back()+v); } } for(ll v:res2){ if(v+res1.back()<=M){ ans=max(ans,res1.back()+v); } } cout<<ans<<endl; }