結果
問題 |
No.2329 Nafmo、イカサマをする
|
ユーザー |
|
提出日時 | 2023-05-29 16:59:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,476 bytes |
コンパイル時間 | 1,295 ms |
コンパイル使用メモリ | 94,612 KB |
実行使用メモリ | 13,824 KB |
最終ジャッジ日時 | 2024-12-28 10:00:06 |
合計ジャッジ時間 | 2,775 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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); vector<ll> tmp; auto dfs=[&](auto f,int idx, int n)->set<ll>{ if(idx==n){ return set<ll>{0}; } set<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); } } set<ll> res; for(ll v:tmpst){ //res.push_back(v); res.insert(v); } return res; }; set<ll> res1=dfs(dfs,0,K/2); set<ll> res2=dfs(dfs,0,K-K/2); ll ans=0; for(ll v1:res1){ ll v=v1+(*res2.rbegin()); if(v>M) continue; ans=max(ans, v ); } for(ll v2:res2){ ll v=v2+(*res1.rbegin()); if(v>M) continue; ans=max(ans, v ); } /* for(ll v1:res1){ for(ll v2:res2){ if(v1+v2>M) continue; ans=max(ans,v1+v2); } } */ cout<<ans<<endl; }