Submission #00131

ソースコード

?
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
#include <iostream>
#include <vector>
#include <algorithm>
struct Item {
int cost;
int value;
};
int main() {
int N, M;
std::cin >> N >> M;
std::vector<Item> items(N);
for (int i = 0; i < N; ++i) {
std::cin >> items[i].cost >> items[i].value;
}
// dp[i][j]: 個数 i までの商品で所持金 j を使ったときの最大満足度
std::vector<std::vector<int>> dp(N + 1, std::vector<int>(M + 1, 0));
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= M; ++j) {
// i番目の商品を買わない場合
dp[i][j] = dp[i - 1][j];
// i番目の商品を買う場合
if (j >= items[i - 1].cost) {
dp[i][j] = std::max(dp[i][j], dp[i - 1][j - items[i - 1].cost] + items[i - 1].value);
}
}
}
std::cout << dp[N][M] << std::endl;
return 0;
}

ステータス

項目 データ
問題 0012 - うっちーとうっちーのおかいもの
ユーザー名 ei2319-Mk.2
投稿日時 2023-11-14 17:07:53
言語 C++17
状態 Runtime Error
得点 0
ソースコード長 945 Byte
最大実行時間 101 ms
最大メモリ使用量 3616 KB

セット

セット 得点 Cases
1 ALL 0 / 50 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00_sample_00.txt AC 24 ms 604 KB
1
00_sample_01.txt AC 17 ms 704 KB
1
00_sample_02.txt AC 20 ms 3616 KB
1
01_nomal_00.txt AC 25 ms 452 KB
1
01_nomal_01.txt AC 25 ms 3232 KB
1
01_nomal_02.txt AC 20 ms 332 KB
1
01_nomal_03.txt AC 19 ms 676 KB
1
01_nomal_04.txt AC 24 ms 512 KB
1
02_hard_00.txt RE 101 ms 488 KB
1
02_hard_01.txt RE 41 ms 588 KB
1