結果
問題 | No.2329 Nafmo、イカサマをする |
ユーザー |
|
提出日時 | 2023-05-29 16:54:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,312 bytes |
コンパイル時間 | 1,079 ms |
コンパイル使用メモリ | 94,616 KB |
実行使用メモリ | 8,620 KB |
最終ジャッジ日時 | 2024-12-28 09:59:26 |
合計ジャッジ時間 | 2,793 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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){ if(v+a>M) continue; 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) continue; ans=max(ans,res2.back()+v); } for(ll v:res2){ if(v+res1.back()>M) continue; ans=max(ans,res1.back()+v); } cout<<ans<<endl; }