Submission #34555

ソースコード

?
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
33
34
35
36
37
38
39
40
41
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i,f,n) for(int i=(f); i<=(n); ++i)
#define outl(x) cout<< (x) << '\n'
int N, W;
int v[1002], w[1002];
int dp[102][10010];
int main()
{
scanf("%d%d", &N, &W);
rep(i, N)
scanf("%d%d", v+i, w+i);
for (int i=N-1; i>=0; --i) {
for (int j=0; j<=W; ++j) {
if (j < w[i]) {
dp[i][j] = dp[i+1][j];
} else {
dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
}
}
}
printf("%d\n", dp[0][W]);
int i=0, rem=W;
while (dp[i][rem] != 0) {
if (dp[i+1][rem] != dp[i][rem]) {
printf("%d ", i+1);
rem -= w[i];
}
++i;
}
}

ステータス

項目 データ
問題 0240 - ナップザック問題(Expert)
ユーザー名 Arumakan_ei1727
投稿日時 2018-05-02 18:39:16
言語 C++11
状態 Accepted
得点 7
ソースコード長 812 Byte
最大実行時間 34 ms
最大メモリ使用量 4652 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
DPL_1_B_in1.txt AC 30 ms 480 KB
1
DPL_1_B_in2.txt AC 30 ms 520 KB
1
DPL_1_B_in3.txt AC 25 ms 588 KB
1
DPL_1_B_in4.txt AC 21 ms 716 KB
1
DPL_1_B_in5.txt AC 20 ms 668 KB
1
DPL_1_B_in6.txt AC 22 ms 624 KB
1
DPL_1_B_in7.txt AC 20 ms 704 KB
1
DPL_1_B_in8.txt AC 20 ms 728 KB
1
DPL_1_B_in9.txt AC 20 ms 736 KB
1
DPL_1_B_in10.txt AC 21 ms 568 KB
1
DPL_1_B_in11.txt AC 23 ms 672 KB
1
DPL_1_B_in12.txt AC 18 ms 736 KB
1
DPL_1_B_in13.txt AC 20 ms 936 KB
1
DPL_1_B_in14.txt AC 24 ms 1240 KB
1
DPL_1_B_in15.txt AC 24 ms 1396 KB
1
DPL_1_B_in16.txt AC 23 ms 1512 KB
1
DPL_1_B_in17.txt AC 22 ms 636 KB
1
DPL_1_B_in18.txt AC 32 ms 988 KB
1
DPL_1_B_in19.txt AC 22 ms 568 KB
1
DPL_1_B_in20.txt AC 20 ms 492 KB
1
DPL_1_B_in21.txt AC 25 ms 1068 KB
1
DPL_1_B_in22.txt AC 25 ms 1728 KB
1
DPL_1_B_in23.txt AC 25 ms 2572 KB
1
DPL_1_B_in24.txt AC 21 ms 2508 KB
1
DPL_1_B_in25.txt AC 18 ms 1036 KB
1
DPL_1_B_in26.txt AC 26 ms 984 KB
1
DPL_1_B_in27.txt AC 22 ms 1048 KB
1
DPL_1_B_in28.txt AC 24 ms 1480 KB
1
DPL_1_B_in29.txt AC 20 ms 2064 KB
1
DPL_1_B_in30.txt AC 27 ms 2980 KB
1
DPL_1_B_in31.txt AC 34 ms 3928 KB
1
DPL_1_B_in32.txt AC 33 ms 4540 KB
1
DPL_1_B_in33.txt AC 22 ms 4564 KB
1
DPL_1_B_in34.txt AC 30 ms 4596 KB
1
DPL_1_B_in35.txt AC 28 ms 4624 KB
1
DPL_1_B_in36.txt AC 23 ms 4652 KB
1