結果
問題 |
No.626 Randomized 01 Knapsack
|
ユーザー |
|
提出日時 | 2018-03-26 19:14:44 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 122 ms / 2,000 ms |
コード長 | 1,028 bytes |
コンパイル時間 | 686 ms |
コンパイル使用メモリ | 38,628 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 03:35:49 |
合計ジャッジ時間 | 1,831 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:50:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 50 | scanf("%d%lld",&n,&m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:51:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 51 | for(i=1;i<=n;i++) scanf("%lld%lld",&item[i].V,&item[i].W); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <cstdio> #include <algorithm> #define V first #define W second using namespace std; typedef pair<long long,long long> pll; int n; long long m,ans; pll item[5010]; bool flag[5010]; bool cmp(pll a,pll b) { return 1.0*a.V/a.W > 1.0*b.V/b.W; } void dfs(long long v,long long w) { int i; long long nv = v,nw = w; for(i=1;i<=n;i++) if(!flag[i]) { if(nw + item[i].W <= m) { nv += item[i].V, nw += item[i].W; if(nw == m) { ans = max(ans,nv); return; } } else { if((long long)(nv + 1.0*(m-nw)/item[i].W*item[i].V) <= ans) return; break; } } ans = max(ans,nv); if(i > n) return; flag[i] = true; dfs(v,w); if(w + item[i].W <= m) dfs(v+item[i].V,w+item[i].W); flag[i] = false; } int main() { int i; scanf("%d%lld",&n,&m); for(i=1;i<=n;i++) scanf("%lld%lld",&item[i].V,&item[i].W); sort(item+1,item+n+1,cmp); dfs(0,0); printf("%lld",ans); return 0; }