結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2017-12-18 13:49:08 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 1,379 bytes |
コンパイル時間 | 1,790 ms |
コンパイル使用メモリ | 162,592 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 03:29:34 |
合計ジャッジ時間 | 2,753 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> using namespace std; using LL = long long int; const int MAX_N = 50005; int N; class Gift{ public: LL V, W; double value; void input() { cin >> V >> W; value = (double)V/(double)W; } bool operator < (const Gift& p) const { return value < p.value; } bool operator > (const Gift& p) const { return value > p.value; } }G[MAX_N]; LL W; LL ans = 0; LL solve(int pos = 0, LL tmpV = 0, LL tmpW = 0) { if((double)ans > tmpV + (double)(W-tmpW)*G[pos].value) { return tmpV; } if(pos == N) { ans = max(ans, tmpV); return tmpV; } double tV = tmpV; int tW = tmpW; for(int i = pos; i < N; i++){ if(tW + G[i].W <= W){ tW += G[i].W; tV += G[i].V; } else{ tV += (double)G[i].V/G[i].W * (W - tW); break; } } if(tV < ans) { return tmpV; } LL ret = 0; if(tmpW + G[pos].W <= W) { ret = max(ret, solve(pos+1, tmpV+G[pos].V, tmpW+G[pos].W)); } ret = max(ret, solve(pos+1, tmpV, tmpW)); ans = max(ret, ans); return ret; } int main() { cin >> N >> W; for(int i = 0; i < N; i++) { G[i].input(); } sort(G, G+N, greater<Gift>()); LL tmpW = 0; for(int i = 0; i < N; i++) { if(tmpW + G[i].W <= W) { tmpW += G[i].W; ans += G[i].V; } } cerr << ans << endl; solve(); cout << ans << endl; return 0; }