답안 #984675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
984675	2024-05-17T01:38:52 Z	Sandarach151	Knapsack (NOI18_knapsack)	C++17	73 / 100	137 ms	262144 KB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int s, n;
    cin >> s >> n;
    int w[n+1], v[n+1], k[n+1];
    for(int i=1; i<=n; i++){
        cin >> v[i] >> w[i] >> k[i];
    }
    vector<vector<pair<int, int> > > ans(n+1, vector<pair<int, int> >(s+1));
    for(int i=0; i<=s; i++){
        ans[0][i] = {0, 0};
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<=s; j++){
            if(j>=w[i]){
                if(ans[i][j-w[i]].second < k[i]){
                    if(ans[i][j-w[i]].first+v[i] > ans[i-1][j].first) {
                        ans[i][j] = {ans[i][j-w[i]].first + v[i], ans[i][j-w[i]].second+1};
                    }
                    else{
                        ans[i][j] = {ans[i-1][j].first, 0};
                    }
                }
                else{
                    for(int kk=0; kk*w[i]<=j && kk<=k[i]; kk++){
                        if(ans[i-1][j-w[i]*kk].first+v[i]*kk > ans[i][j].first){
                            ans[i][j] = {ans[i-1][j-w[i]*kk].first+v[i]*kk, kk};
                        }
                    }
                }
            }
            else{
                ans[i][j] = ans[i-1][j];
            }
        }
    }
    // for(int i=-1; i<=s; i++){
    //     printf("%5d", i);
    // }
    // printf("\n");
    // for(int i=0; i<=n; i++){
    //     printf("%3d: ", i);
    //     for(int j=0; j<=s; j++){
    //         printf("%5d", ans[i][j].first);
    //     }
    //     printf("\n");
    // }
    cout << ans[n][s].first << '\n';
}

Subtask #1

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	596 KB	Output is correct

Subtask #2

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	2 ms	3420 KB	Output is correct
3	Correct	2 ms	3416 KB	Output is correct
4	Correct	2 ms	3420 KB	Output is correct
5	Correct	3 ms	3572 KB	Output is correct
6	Correct	2 ms	3420 KB	Output is correct
7	Correct	2 ms	3420 KB	Output is correct
8	Correct	2 ms	3420 KB	Output is correct
9	Correct	2 ms	3420 KB	Output is correct
10	Correct	2 ms	3420 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	2 ms	3420 KB	Output is correct
3	Correct	2 ms	3416 KB	Output is correct
4	Correct	2 ms	3420 KB	Output is correct
5	Correct	3 ms	3572 KB	Output is correct
6	Correct	2 ms	3420 KB	Output is correct
7	Correct	2 ms	3420 KB	Output is correct
8	Correct	2 ms	3420 KB	Output is correct
9	Correct	2 ms	3420 KB	Output is correct
10	Correct	2 ms	3420 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	4 ms	3420 KB	Output is correct
13	Correct	2 ms	3420 KB	Output is correct
14	Correct	2 ms	3420 KB	Output is correct
15	Correct	2 ms	3420 KB	Output is correct
16	Correct	2 ms	3420 KB	Output is correct
17	Correct	2 ms	3384 KB	Output is correct
18	Correct	2 ms	3416 KB	Output is correct
19	Correct	2 ms	3420 KB	Output is correct
20	Correct	2 ms	3420 KB	Output is correct

Subtask #4

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	596 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	2 ms	3420 KB	Output is correct
7	Correct	2 ms	3416 KB	Output is correct
8	Correct	2 ms	3420 KB	Output is correct
9	Correct	3 ms	3572 KB	Output is correct
10	Correct	2 ms	3420 KB	Output is correct
11	Correct	2 ms	3420 KB	Output is correct
12	Correct	2 ms	3420 KB	Output is correct
13	Correct	2 ms	3420 KB	Output is correct
14	Correct	2 ms	3420 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	4 ms	3420 KB	Output is correct
17	Correct	2 ms	3420 KB	Output is correct
18	Correct	2 ms	3420 KB	Output is correct
19	Correct	2 ms	3420 KB	Output is correct
20	Correct	2 ms	3420 KB	Output is correct
21	Correct	2 ms	3384 KB	Output is correct
22	Correct	2 ms	3416 KB	Output is correct
23	Correct	2 ms	3420 KB	Output is correct
24	Correct	2 ms	3420 KB	Output is correct
25	Correct	0 ms	344 KB	Output is correct
26	Correct	12 ms	3420 KB	Output is correct
27	Correct	2 ms	3420 KB	Output is correct
28	Correct	2 ms	3420 KB	Output is correct
29	Correct	2 ms	3416 KB	Output is correct
30	Correct	2 ms	3420 KB	Output is correct
31	Correct	2 ms	3420 KB	Output is correct
32	Correct	2 ms	3416 KB	Output is correct
33	Correct	3 ms	3420 KB	Output is correct
34	Correct	2 ms	3420 KB	Output is correct

Subtask #5

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	596 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	2 ms	3420 KB	Output is correct
7	Correct	2 ms	3416 KB	Output is correct
8	Correct	2 ms	3420 KB	Output is correct
9	Correct	3 ms	3572 KB	Output is correct
10	Correct	2 ms	3420 KB	Output is correct
11	Correct	2 ms	3420 KB	Output is correct
12	Correct	2 ms	3420 KB	Output is correct
13	Correct	2 ms	3420 KB	Output is correct
14	Correct	2 ms	3420 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Correct	4 ms	3420 KB	Output is correct
17	Correct	2 ms	3420 KB	Output is correct
18	Correct	2 ms	3420 KB	Output is correct
19	Correct	2 ms	3420 KB	Output is correct
20	Correct	2 ms	3420 KB	Output is correct
21	Correct	2 ms	3384 KB	Output is correct
22	Correct	2 ms	3416 KB	Output is correct
23	Correct	2 ms	3420 KB	Output is correct
24	Correct	2 ms	3420 KB	Output is correct
25	Correct	0 ms	344 KB	Output is correct
26	Correct	12 ms	3420 KB	Output is correct
27	Correct	2 ms	3420 KB	Output is correct
28	Correct	2 ms	3420 KB	Output is correct
29	Correct	2 ms	3416 KB	Output is correct
30	Correct	2 ms	3420 KB	Output is correct
31	Correct	2 ms	3420 KB	Output is correct
32	Correct	2 ms	3416 KB	Output is correct
33	Correct	3 ms	3420 KB	Output is correct
34	Correct	2 ms	3420 KB	Output is correct
35	Correct	21 ms	9896 KB	Output is correct
36	Runtime error	137 ms	262144 KB	Execution killed with signal 9
37	Halted	0 ms	0 KB	-