結果

問題 No.626 Randomized 01 Knapsack
ユーザー ikdikd
提出日時 2017-12-15 23:07:49
言語 C++11
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 481 bytes
コンパイル時間 882 ms
コンパイル使用メモリ 68,044 KB
実行使用メモリ 515,912 KB
最終ジャッジ日時 2024-12-15 19:48:59
合計ジャッジ時間 59,108 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 MLE * 1 TLE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<map>
using namespace std;
#define int long long
int n, wmax;
int v[5000], w[5000];

map<pair<int, int>, int> mm;
int fun(int i, int wsum){
  if(i==n) return 0;
  pair<int, int> k={i, wsum};
  if(mm.count(k)) return mm[k];
  int ret=fun(i+1, wsum);
  if(wsum+w[i]<=wmax) ret=max(ret, fun(i+1, wsum+w[i])+v[i]);
  return mm[k]=ret;
}

signed main(){

  cin>> n>> wmax;
  for(int i=0; i<n; i++) cin>> v[i]>> w[i];

  cout<< fun(0, 0)<< endl;

  return 0;
}
0