Submission #528386

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
528386	2022-02-20T08:33:29 Z	louiskwok	Knapsack (NOI18_knapsack)	C++17	29 / 100	3 ms	1868 KB

knapsack

#include <bits/stdc++.h>
using namespace std;
long long v[100005],w[100005],k[100005];
long long dp[100005][2005],ans;
int main() {
    long long s,n;
    cin >> s >> n;
    for (int i=1;i<=n;i++) cin >> v[i] >> w[i] >> k[i];
    for (int i=1;i<=n;i++) {
        for (int j=0;j<=s;j++) {
            dp[i][j] = max(dp[i][j],dp[i-1][j]);
            long long num = min(k[i],(s-j)/w[i]);
            dp[i][j+num*w[i]] = max(dp[i][j+num*w[i]],dp[i-1][j]+v[i]*num);
        }
    }
    for (int i=0;i<=s;i++) ans = max(ans,dp[n][i]);
    cout << ans << endl;
    return 0;
}

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	716 KB	Output is correct
2	Correct	3 ms	1868 KB	Output is correct
3	Correct	3 ms	1740 KB	Output is correct
4	Correct	3 ms	1868 KB	Output is correct
5	Correct	2 ms	1868 KB	Output is correct
6	Correct	3 ms	1868 KB	Output is correct
7	Correct	3 ms	1832 KB	Output is correct
8	Correct	3 ms	1740 KB	Output is correct
9	Correct	2 ms	1740 KB	Output is correct
10	Correct	3 ms	1868 KB	Output is correct

Subtask #3

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	716 KB	Output is correct
2	Correct	3 ms	1868 KB	Output is correct
3	Correct	3 ms	1740 KB	Output is correct
4	Correct	3 ms	1868 KB	Output is correct
5	Correct	2 ms	1868 KB	Output is correct
6	Correct	3 ms	1868 KB	Output is correct
7	Correct	3 ms	1832 KB	Output is correct
8	Correct	3 ms	1740 KB	Output is correct
9	Correct	2 ms	1740 KB	Output is correct
10	Correct	3 ms	1868 KB	Output is correct
11	Correct	1 ms	716 KB	Output is correct
12	Correct	3 ms	1868 KB	Output is correct
13	Correct	3 ms	1740 KB	Output is correct
14	Correct	2 ms	1868 KB	Output is correct
15	Correct	3 ms	1764 KB	Output is correct
16	Incorrect	2 ms	1840 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	716 KB	Output is correct
6	Correct	3 ms	1868 KB	Output is correct
7	Correct	3 ms	1740 KB	Output is correct
8	Correct	3 ms	1868 KB	Output is correct
9	Correct	2 ms	1868 KB	Output is correct
10	Correct	3 ms	1868 KB	Output is correct
11	Correct	3 ms	1832 KB	Output is correct
12	Correct	3 ms	1740 KB	Output is correct
13	Correct	2 ms	1740 KB	Output is correct
14	Correct	3 ms	1868 KB	Output is correct
15	Correct	1 ms	716 KB	Output is correct
16	Correct	3 ms	1868 KB	Output is correct
17	Correct	3 ms	1740 KB	Output is correct
18	Correct	2 ms	1868 KB	Output is correct
19	Correct	3 ms	1764 KB	Output is correct
20	Incorrect	2 ms	1840 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	716 KB	Output is correct
6	Correct	3 ms	1868 KB	Output is correct
7	Correct	3 ms	1740 KB	Output is correct
8	Correct	3 ms	1868 KB	Output is correct
9	Correct	2 ms	1868 KB	Output is correct
10	Correct	3 ms	1868 KB	Output is correct
11	Correct	3 ms	1832 KB	Output is correct
12	Correct	3 ms	1740 KB	Output is correct
13	Correct	2 ms	1740 KB	Output is correct
14	Correct	3 ms	1868 KB	Output is correct
15	Correct	1 ms	716 KB	Output is correct
16	Correct	3 ms	1868 KB	Output is correct
17	Correct	3 ms	1740 KB	Output is correct
18	Correct	2 ms	1868 KB	Output is correct
19	Correct	3 ms	1764 KB	Output is correct
20	Incorrect	2 ms	1840 KB	Output isn't correct
21	Halted	0 ms	0 KB	-