Submission #52858

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define int long long
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
int n,W;
vector<int> v(150),w(150);
vector<vector<int> > mem(150,vector<int>(10050,-1));
int dp(int i,int j){
if(i == n) return 0;
if(mem[i][j] != -1) return mem[i][j];
if(j + w[i] > W) return mem[i][j] = dp(i + 1,j);
return mem[i][j] = max(dp(i + 1,j + w[i]) + v[i] , dp(i + 1,j));
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> W;
rep(i,n){
cin >> v[i] >> w[i];
}
cout << dp(0,0) << '\n';
return 0;
}

ステータス

項目 データ
問題 0238 - ナップザック問題(Easy)
ユーザー名 ei1903
投稿日時 2019-08-19 10:46:38
言語 C++14
状態 Accepted
得点 3
ソースコード長 776 Byte
最大実行時間 44 ms
最大メモリ使用量 12648 KB

セット

セット 得点 Cases
1 ALL 3 / 3 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
DPL_1_B_in1.txt AC 26 ms 12508 KB
1
DPL_1_B_in2.txt AC 21 ms 12368 KB
1
DPL_1_B_in3.txt AC 26 ms 12360 KB
1
DPL_1_B_in4.txt AC 23 ms 12460 KB
1
DPL_1_B_in5.txt AC 26 ms 12468 KB
1
DPL_1_B_in6.txt AC 28 ms 12480 KB
1
DPL_1_B_in7.txt AC 25 ms 12616 KB
1
DPL_1_B_in8.txt AC 30 ms 12632 KB
1
DPL_1_B_in9.txt AC 21 ms 12648 KB
1
DPL_1_B_in10.txt AC 22 ms 12388 KB
1
DPL_1_B_in11.txt AC 21 ms 12272 KB
1
DPL_1_B_in12.txt AC 27 ms 12284 KB
1
DPL_1_B_in13.txt AC 26 ms 12288 KB
1
DPL_1_B_in14.txt AC 27 ms 12428 KB
1
DPL_1_B_in15.txt AC 34 ms 12312 KB
1
DPL_1_B_in16.txt AC 22 ms 12328 KB
1
DPL_1_B_in17.txt AC 29 ms 12344 KB
1
DPL_1_B_in18.txt AC 29 ms 12352 KB
1
DPL_1_B_in19.txt AC 29 ms 12360 KB
1
DPL_1_B_in20.txt AC 26 ms 12380 KB
1
DPL_1_B_in21.txt AC 26 ms 12392 KB
1
DPL_1_B_in22.txt AC 29 ms 12404 KB
1
DPL_1_B_in23.txt AC 31 ms 12412 KB
1
DPL_1_B_in24.txt AC 32 ms 12556 KB
1
DPL_1_B_in25.txt AC 25 ms 12564 KB
1
DPL_1_B_in26.txt AC 26 ms 12452 KB
1
DPL_1_B_in27.txt AC 29 ms 12336 KB
1
DPL_1_B_in28.txt AC 26 ms 12472 KB
1
DPL_1_B_in29.txt AC 26 ms 12480 KB
1
DPL_1_B_in30.txt AC 34 ms 12372 KB
1
DPL_1_B_in31.txt AC 32 ms 12384 KB
1
DPL_1_B_in32.txt AC 44 ms 12524 KB
1
DPL_1_B_in33.txt AC 25 ms 12532 KB
1
DPL_1_B_in34.txt AC 29 ms 12416 KB
1
DPL_1_B_in35.txt AC 32 ms 12432 KB
1
DPL_1_B_in36.txt AC 35 ms 12444 KB
1