답안 #975653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975653	2024-05-05T16:12:32 Z	vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	524 ms	161876 KB

knapsack

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

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define AC ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define pb push_back
const int inf=INT_MAX;

vector<pii> a[2007];
vector<pii> item;
int dp[20007][2007];
int C, n;

int knapsack(int i, int C){
	if(C < 0)return -inf;
	if(i==item.size())return 0;
	if(dp[i][C] != -1)return dp[i][C];
	
	
	int w = item[i].sc, v= item[i].fs;
	return dp[i][C]= max(knapsack(i+1, C), knapsack(i+1, C-w)+v);
}
int main() {   
    AC
    cin >> C >> n;
    for(int i=0; i<n; i++){
    	int v, w, k;
    	cin >> v >> w >> k;
    	a[w].pb({v,k});
    }
    for(int w=1; w<=2000; w++){
    	sort(a[w].begin(), a[w].end());
    	int used = ceil(C/w);
    	while(used and !a[w].empty()){
    		auto &[v, k] = a[w].back();
    		item.pb({a[w].back().fs, w});
    		used--, k--;
    		if(k==0)a[w].pop_back();
    	}
    }
    memset(dp, -1, sizeof(dp));
    cout << knapsack(0, C);
}

Compilation message

knapsack.cpp: In function 'int knapsack(int, int)':
knapsack.cpp:20:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  if(i==item.size())return 0;
      |     ~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	157420 KB	Output is correct
2	Correct	20 ms	157524 KB	Output is correct
3	Correct	21 ms	157520 KB	Output is correct
4	Correct	22 ms	157524 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	157484 KB	Output is correct
2	Correct	19 ms	157532 KB	Output is correct
3	Correct	20 ms	157532 KB	Output is correct
4	Correct	20 ms	157676 KB	Output is correct
5	Correct	21 ms	157532 KB	Output is correct
6	Correct	21 ms	157532 KB	Output is correct
7	Correct	20 ms	157532 KB	Output is correct
8	Correct	22 ms	157444 KB	Output is correct
9	Correct	21 ms	157784 KB	Output is correct
10	Correct	21 ms	157532 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	157484 KB	Output is correct
2	Correct	19 ms	157532 KB	Output is correct
3	Correct	20 ms	157532 KB	Output is correct
4	Correct	20 ms	157676 KB	Output is correct
5	Correct	21 ms	157532 KB	Output is correct
6	Correct	21 ms	157532 KB	Output is correct
7	Correct	20 ms	157532 KB	Output is correct
8	Correct	22 ms	157444 KB	Output is correct
9	Correct	21 ms	157784 KB	Output is correct
10	Correct	21 ms	157532 KB	Output is correct
11	Correct	21 ms	157520 KB	Output is correct
12	Correct	23 ms	157532 KB	Output is correct
13	Correct	20 ms	157532 KB	Output is correct
14	Correct	19 ms	157492 KB	Output is correct
15	Correct	21 ms	157788 KB	Output is correct
16	Correct	22 ms	157524 KB	Output is correct
17	Correct	21 ms	157484 KB	Output is correct
18	Correct	22 ms	157628 KB	Output is correct
19	Correct	23 ms	157532 KB	Output is correct
20	Correct	23 ms	157524 KB	Output is correct

Subtask #4
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	157420 KB	Output is correct
2	Correct	20 ms	157524 KB	Output is correct
3	Correct	21 ms	157520 KB	Output is correct
4	Correct	22 ms	157524 KB	Output is correct
5	Correct	21 ms	157484 KB	Output is correct
6	Correct	19 ms	157532 KB	Output is correct
7	Correct	20 ms	157532 KB	Output is correct
8	Correct	20 ms	157676 KB	Output is correct
9	Correct	21 ms	157532 KB	Output is correct
10	Correct	21 ms	157532 KB	Output is correct
11	Correct	20 ms	157532 KB	Output is correct
12	Correct	22 ms	157444 KB	Output is correct
13	Correct	21 ms	157784 KB	Output is correct
14	Correct	21 ms	157532 KB	Output is correct
15	Correct	21 ms	157520 KB	Output is correct
16	Correct	23 ms	157532 KB	Output is correct
17	Correct	20 ms	157532 KB	Output is correct
18	Correct	19 ms	157492 KB	Output is correct
19	Correct	21 ms	157788 KB	Output is correct
20	Correct	22 ms	157524 KB	Output is correct
21	Correct	21 ms	157484 KB	Output is correct
22	Correct	22 ms	157628 KB	Output is correct
23	Correct	23 ms	157532 KB	Output is correct
24	Correct	23 ms	157524 KB	Output is correct
25	Correct	20 ms	157532 KB	Output is correct
26	Correct	35 ms	157528 KB	Output is correct
27	Correct	20 ms	157568 KB	Output is correct
28	Correct	20 ms	157532 KB	Output is correct
29	Correct	20 ms	157448 KB	Output is correct
30	Correct	26 ms	157532 KB	Output is correct
31	Correct	21 ms	157524 KB	Output is correct
32	Correct	21 ms	157532 KB	Output is correct
33	Correct	22 ms	157532 KB	Output is correct
34	Correct	22 ms	157576 KB	Output is correct

Subtask #5
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	157420 KB	Output is correct
2	Correct	20 ms	157524 KB	Output is correct
3	Correct	21 ms	157520 KB	Output is correct
4	Correct	22 ms	157524 KB	Output is correct
5	Correct	21 ms	157484 KB	Output is correct
6	Correct	19 ms	157532 KB	Output is correct
7	Correct	20 ms	157532 KB	Output is correct
8	Correct	20 ms	157676 KB	Output is correct
9	Correct	21 ms	157532 KB	Output is correct
10	Correct	21 ms	157532 KB	Output is correct
11	Correct	20 ms	157532 KB	Output is correct
12	Correct	22 ms	157444 KB	Output is correct
13	Correct	21 ms	157784 KB	Output is correct
14	Correct	21 ms	157532 KB	Output is correct
15	Correct	21 ms	157520 KB	Output is correct
16	Correct	23 ms	157532 KB	Output is correct
17	Correct	20 ms	157532 KB	Output is correct
18	Correct	19 ms	157492 KB	Output is correct
19	Correct	21 ms	157788 KB	Output is correct
20	Correct	22 ms	157524 KB	Output is correct
21	Correct	21 ms	157484 KB	Output is correct
22	Correct	22 ms	157628 KB	Output is correct
23	Correct	23 ms	157532 KB	Output is correct
24	Correct	23 ms	157524 KB	Output is correct
25	Correct	20 ms	157532 KB	Output is correct
26	Correct	35 ms	157528 KB	Output is correct
27	Correct	20 ms	157568 KB	Output is correct
28	Correct	20 ms	157532 KB	Output is correct
29	Correct	20 ms	157448 KB	Output is correct
30	Correct	26 ms	157532 KB	Output is correct
31	Correct	21 ms	157524 KB	Output is correct
32	Correct	21 ms	157532 KB	Output is correct
33	Correct	22 ms	157532 KB	Output is correct
34	Correct	22 ms	157576 KB	Output is correct
35	Correct	40 ms	159424 KB	Output is correct
36	Correct	57 ms	160204 KB	Output is correct
37	Correct	54 ms	159692 KB	Output is correct
38	Correct	41 ms	159924 KB	Output is correct
39	Correct	45 ms	160500 KB	Output is correct
40	Correct	501 ms	161876 KB	Output is correct
41	Correct	317 ms	160596 KB	Output is correct
42	Correct	330 ms	160792 KB	Output is correct
43	Correct	452 ms	161104 KB	Output is correct
44	Correct	524 ms	161112 KB	Output is correct
45	Correct	58 ms	160928 KB	Output is correct
46	Correct	46 ms	160464 KB	Output is correct
47	Correct	95 ms	161164 KB	Output is correct
48	Correct	283 ms	161308 KB	Output is correct
49	Correct	42 ms	160512 KB	Output is correct
50	Correct	268 ms	161108 KB	Output is correct

답안 #975653

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 17.0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 24.0 / 24.0

Subtask #5 27.0 / 27.0

Subtask #1
12.0 / 12.0

Subtask #2
17.0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
24.0 / 24.0

Subtask #5
27.0 / 27.0