Submission #82001

ソースコード

?
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
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
int main(){
ll n,mc,mw;
cin >> n >> mc >> mw;//個数 価格限界 重さ限界
vector<ll> c(n+1),w(n+1),y(n+1);
vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(mc+1,vector<ll>(mw+1)));
//i個まで買った時j円使った時重さがkであるときの最大のおいしさ
for(ll i=1;i<=n;i++)cin >> c[i] >> w[i] >> y[i];//価格 重さ 美味しさ
//3次元dp開始
for(ll i=1;i<=n;i++){
for(ll j=1;j<=mc;j++){
for(ll k=mw;k>0;k--){
dp[i][j][k] = max({dp[i][j-1][k],dp[i][j][k-1],dp[i-1][j][k]});
if(j - c[i]>=0&&k - w[i]>=0){
dp[i][j][k] = max(dp[i][j][k] , dp[i-1][j-c[i]][k-w[i]] + y[i]);
}
}
}
}
// for(ll i=0;i<=n;i++){
// cout << i << endl;
// for(ll j=0;j<=mc;j++){
// for(ll k=0;k<=mw;k++){
// cout << dp[i][j][k] << " ";
// }
// cout << endl;
// }
// cout << c[i] << " " << w[i] << " " << y[i] << endl;
// cout << endl;
// }
cout << dp[n][mc][mw] << endl;
}

ステータス

項目 データ
問題 1888 - Knapsack3
ユーザー名 DAI_0110
投稿日時 2024-12-14 12:04:46
言語 C++17
状態 Accepted
得点 10
ソースコード長 1248 Byte
最大実行時間 148 ms
最大メモリ使用量 151792 KB

セット

セット 得点 Cases
1 ALL 3 / 3 *
2 小課題2 4 / 4 input6.txt, input7.txt
3 小課題１ 3 / 3 input1.txt, input2.txt, input3.txt, input4.txt, input5.txt

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input1.txt AC 28 ms 604 KB
1
3
input2.txt AC 19 ms 548 KB
1
3
input3.txt AC 19 ms 604 KB
1
3
input4.txt AC 32 ms 1856 KB
1
3
input5.txt AC 27 ms 8600 KB
1
3
input6.txt AC 26 ms 5448 KB
1
2
input7.txt AC 22 ms 3440 KB
1
2
input8.txt AC 25 ms 3952 KB
1
input9.txt AC 148 ms 151792 KB
1
input10.txt AC 40 ms 28688 KB
1