oj.uz

Submission #725404

# Submission time Handle Problem Language Result Execution time Memory
725404 2023-04-17T11:24:37 Z Mohamed_Kachef06 Knapsack (NOI18_knapsack) C++17
100 / 100
 815 ms 177032 KB 
#include <bits/stdc++.h>
using namespace std;
#define MODY ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int , int>
#define A first
#define B second
#define pb push_back
 
int n , s;
vector<vector<pii>> vec(2001);
vector<pii> a;
int dp[22001][2001];
int knapsack(int i , int w){
    if (i==-1) return 0 ;
    if (~dp[i][w]) return dp[i][w];
    int x = 0 , y = 0;
    if (w>=a[i].A) x = knapsack(i-1 , w-a[i].A) + a[i].B;
    y = knapsack(i-1 , w);
    return dp[i][w] = max(x, y);
}
signed main(){
    memset(dp , -1 , sizeof dp);
    cin >> s >> n;
    for (int i = 1 ; i<=n ; i++){
        int v , w , k;
        cin >> v >> w >> k;
        vec[w].pb({v , k});
    }
    for (int i = 1 ; i<=s ; i++) sort(vec[i].begin() , vec[i].end() , greater<pii>());
    for (int i = 1 ; i<=s ; i++){
        int copies = 0;
        for (auto j : vec[i]){
            while(copies < s/i && j.B) { a.pb({i , j.A}); j.B--; copies++; }
        }
    }
    cout << knapsack(a.size()-1 , s);
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 172624 KB Output is correct
2 Correct 75 ms 172600 KB Output is correct
3 Correct 64 ms 172632 KB Output is correct
4 Correct 63 ms 172552 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 172564 KB Output is correct
2 Correct 67 ms 172632 KB Output is correct
3 Correct 66 ms 172544 KB Output is correct
4 Correct 65 ms 172592 KB Output is correct
5 Correct 68 ms 172632 KB Output is correct
6 Correct 67 ms 172540 KB Output is correct
7 Correct 78 ms 172552 KB Output is correct
8 Correct 65 ms 172620 KB Output is correct
9 Correct 65 ms 172608 KB Output is correct
10 Correct 65 ms 172532 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 172564 KB Output is correct
2 Correct 67 ms 172632 KB Output is correct
3 Correct 66 ms 172544 KB Output is correct
4 Correct 65 ms 172592 KB Output is correct
5 Correct 68 ms 172632 KB Output is correct
6 Correct 67 ms 172540 KB Output is correct
7 Correct 78 ms 172552 KB Output is correct
8 Correct 65 ms 172620 KB Output is correct
9 Correct 65 ms 172608 KB Output is correct
10 Correct 65 ms 172532 KB Output is correct
11 Correct 68 ms 172520 KB Output is correct
12 Correct 71 ms 172584 KB Output is correct
13 Correct 65 ms 172568 KB Output is correct
14 Correct 71 ms 172620 KB Output is correct
15 Correct 68 ms 172608 KB Output is correct
16 Correct 80 ms 172552 KB Output is correct
17 Correct 73 ms 172632 KB Output is correct
18 Correct 70 ms 172616 KB Output is correct
19 Correct 73 ms 172620 KB Output is correct
20 Correct 72 ms 172624 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 172624 KB Output is correct
2 Correct 75 ms 172600 KB Output is correct
3 Correct 64 ms 172632 KB Output is correct
4 Correct 63 ms 172552 KB Output is correct
5 Correct 71 ms 172564 KB Output is correct
6 Correct 67 ms 172632 KB Output is correct
7 Correct 66 ms 172544 KB Output is correct
8 Correct 65 ms 172592 KB Output is correct
9 Correct 68 ms 172632 KB Output is correct
10 Correct 67 ms 172540 KB Output is correct
11 Correct 78 ms 172552 KB Output is correct
12 Correct 65 ms 172620 KB Output is correct
13 Correct 65 ms 172608 KB Output is correct
14 Correct 65 ms 172532 KB Output is correct
15 Correct 68 ms 172520 KB Output is correct
16 Correct 71 ms 172584 KB Output is correct
17 Correct 65 ms 172568 KB Output is correct
18 Correct 71 ms 172620 KB Output is correct
19 Correct 68 ms 172608 KB Output is correct
20 Correct 80 ms 172552 KB Output is correct
21 Correct 73 ms 172632 KB Output is correct
22 Correct 70 ms 172616 KB Output is correct
23 Correct 73 ms 172620 KB Output is correct
24 Correct 72 ms 172624 KB Output is correct
25 Correct 81 ms 172600 KB Output is correct
26 Correct 102 ms 172792 KB Output is correct
27 Correct 67 ms 172740 KB Output is correct
28 Correct 65 ms 172580 KB Output is correct
29 Correct 64 ms 172624 KB Output is correct
30 Correct 74 ms 172592 KB Output is correct
31 Correct 81 ms 172616 KB Output is correct
32 Correct 71 ms 172552 KB Output is correct
33 Correct 74 ms 172608 KB Output is correct
34 Correct 72 ms 172628 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 172624 KB Output is correct
2 Correct 75 ms 172600 KB Output is correct
3 Correct 64 ms 172632 KB Output is correct
4 Correct 63 ms 172552 KB Output is correct
5 Correct 71 ms 172564 KB Output is correct
6 Correct 67 ms 172632 KB Output is correct
7 Correct 66 ms 172544 KB Output is correct
8 Correct 65 ms 172592 KB Output is correct
9 Correct 68 ms 172632 KB Output is correct
10 Correct 67 ms 172540 KB Output is correct
11 Correct 78 ms 172552 KB Output is correct
12 Correct 65 ms 172620 KB Output is correct
13 Correct 65 ms 172608 KB Output is correct
14 Correct 65 ms 172532 KB Output is correct
15 Correct 68 ms 172520 KB Output is correct
16 Correct 71 ms 172584 KB Output is correct
17 Correct 65 ms 172568 KB Output is correct
18 Correct 71 ms 172620 KB Output is correct
19 Correct 68 ms 172608 KB Output is correct
20 Correct 80 ms 172552 KB Output is correct
21 Correct 73 ms 172632 KB Output is correct
22 Correct 70 ms 172616 KB Output is correct
23 Correct 73 ms 172620 KB Output is correct
24 Correct 72 ms 172624 KB Output is correct
25 Correct 81 ms 172600 KB Output is correct
26 Correct 102 ms 172792 KB Output is correct
27 Correct 67 ms 172740 KB Output is correct
28 Correct 65 ms 172580 KB Output is correct
29 Correct 64 ms 172624 KB Output is correct
30 Correct 74 ms 172592 KB Output is correct
31 Correct 81 ms 172616 KB Output is correct
32 Correct 71 ms 172552 KB Output is correct
33 Correct 74 ms 172608 KB Output is correct
34 Correct 72 ms 172628 KB Output is correct
35 Correct 136 ms 174572 KB Output is correct
36 Correct 171 ms 174960 KB Output is correct
37 Correct 150 ms 174644 KB Output is correct
38 Correct 132 ms 174920 KB Output is correct
39 Correct 179 ms 175912 KB Output is correct
40 Correct 815 ms 177032 KB Output is correct
41 Correct 431 ms 175824 KB Output is correct
42 Correct 443 ms 175856 KB Output is correct
43 Correct 747 ms 176296 KB Output is correct
44 Correct 731 ms 176316 KB Output is correct
45 Correct 171 ms 176080 KB Output is correct
46 Correct 165 ms 175376 KB Output is correct
47 Correct 179 ms 176144 KB Output is correct
48 Correct 319 ms 176408 KB Output is correct
49 Correct 180 ms 175684 KB Output is correct
50 Correct 535 ms 176316 KB Output is correct