oj.uz

Submission #499375

# Submission time Handle Problem Language Result Execution time Memory
499375 2021-12-28T07:50:23 Z MohammadAghil Knapsack (NOI18_knapsack) C++17
100 / 100
 90 ms 33236 KB 
#include <bits/stdc++.h>
using  namespace std;
typedef  long long ll;
typedef  long double ld;
typedef  pair<int, int> pp;
#define  rep(i,l,r) for(int i = (l); i < r; i++)
#define  per(i,r,l) for(int i = (r); i >= l; i--)
#define  all(x) x.begin(), x.end()
#define  sz(x) (int)(x).size()
#define  pb push_back
#define  ff first
#define  ss second 
 
const ll mod = 1e9 + 7, maxn = 2e2 + 5, inf = ll(1e18) + 5;

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    int s, n; cin >> s >> n;
    vector<vector<pp>> a(s + 1);
    rep(i,0,n){
        int w, v, k; cin >> v >> w >> k;
        k = min(k, s); 
        a[w].pb({v, k});
    }
    vector<vector<ll>> dp(s + 1, vector<ll>(s + 1));
    rep(i,1,s + 1){
        sort(all(a[i])); reverse(all(a[i]));
        vector<ll> prf(s/i + 1);
        int pt = 1;
        for(auto [v, k]: a[i]){
            while(k-- && pt != sz(prf)) prf[pt] = prf[pt-1] + v, pt++;
        }
        rep(j,1,s + 1){
            rep(k,0,sz(prf)){
                if(j < k*i) break;
                dp[i][j] = max(dp[i][j], dp[i-1][j-k*i] + prf[k]);
            }
        }
    }   
    cout << dp[s][s] << '\n';
    return 0; 
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12332 KB Output is correct
2 Correct 16 ms 12332 KB Output is correct
3 Correct 20 ms 12404 KB Output is correct
4 Correct 17 ms 12328 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 41 ms 31776 KB Output is correct
3 Correct 42 ms 31692 KB Output is correct
4 Correct 43 ms 31660 KB Output is correct
5 Correct 44 ms 31660 KB Output is correct
6 Correct 39 ms 31776 KB Output is correct
7 Correct 40 ms 31772 KB Output is correct
8 Correct 42 ms 31692 KB Output is correct
9 Correct 45 ms 31696 KB Output is correct
10 Correct 39 ms 31692 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 41 ms 31776 KB Output is correct
3 Correct 42 ms 31692 KB Output is correct
4 Correct 43 ms 31660 KB Output is correct
5 Correct 44 ms 31660 KB Output is correct
6 Correct 39 ms 31776 KB Output is correct
7 Correct 40 ms 31772 KB Output is correct
8 Correct 42 ms 31692 KB Output is correct
9 Correct 45 ms 31696 KB Output is correct
10 Correct 39 ms 31692 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 41 ms 31740 KB Output is correct
13 Correct 38 ms 31692 KB Output is correct
14 Correct 48 ms 31776 KB Output is correct
15 Correct 39 ms 31648 KB Output is correct
16 Correct 43 ms 31740 KB Output is correct
17 Correct 40 ms 31692 KB Output is correct
18 Correct 40 ms 31708 KB Output is correct
19 Correct 40 ms 31692 KB Output is correct
20 Correct 39 ms 31692 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12332 KB Output is correct
2 Correct 16 ms 12332 KB Output is correct
3 Correct 20 ms 12404 KB Output is correct
4 Correct 17 ms 12328 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 41 ms 31776 KB Output is correct
7 Correct 42 ms 31692 KB Output is correct
8 Correct 43 ms 31660 KB Output is correct
9 Correct 44 ms 31660 KB Output is correct
10 Correct 39 ms 31776 KB Output is correct
11 Correct 40 ms 31772 KB Output is correct
12 Correct 42 ms 31692 KB Output is correct
13 Correct 45 ms 31696 KB Output is correct
14 Correct 39 ms 31692 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 41 ms 31740 KB Output is correct
17 Correct 38 ms 31692 KB Output is correct
18 Correct 48 ms 31776 KB Output is correct
19 Correct 39 ms 31648 KB Output is correct
20 Correct 43 ms 31740 KB Output is correct
21 Correct 40 ms 31692 KB Output is correct
22 Correct 40 ms 31708 KB Output is correct
23 Correct 40 ms 31692 KB Output is correct
24 Correct 39 ms 31692 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 42 ms 31620 KB Output is correct
27 Correct 40 ms 31768 KB Output is correct
28 Correct 41 ms 31716 KB Output is correct
29 Correct 49 ms 31708 KB Output is correct
30 Correct 46 ms 31692 KB Output is correct
31 Correct 39 ms 31760 KB Output is correct
32 Correct 40 ms 31668 KB Output is correct
33 Correct 40 ms 31656 KB Output is correct
34 Correct 41 ms 31600 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12332 KB Output is correct
2 Correct 16 ms 12332 KB Output is correct
3 Correct 20 ms 12404 KB Output is correct
4 Correct 17 ms 12328 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 41 ms 31776 KB Output is correct
7 Correct 42 ms 31692 KB Output is correct
8 Correct 43 ms 31660 KB Output is correct
9 Correct 44 ms 31660 KB Output is correct
10 Correct 39 ms 31776 KB Output is correct
11 Correct 40 ms 31772 KB Output is correct
12 Correct 42 ms 31692 KB Output is correct
13 Correct 45 ms 31696 KB Output is correct
14 Correct 39 ms 31692 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 41 ms 31740 KB Output is correct
17 Correct 38 ms 31692 KB Output is correct
18 Correct 48 ms 31776 KB Output is correct
19 Correct 39 ms 31648 KB Output is correct
20 Correct 43 ms 31740 KB Output is correct
21 Correct 40 ms 31692 KB Output is correct
22 Correct 40 ms 31708 KB Output is correct
23 Correct 40 ms 31692 KB Output is correct
24 Correct 39 ms 31692 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 42 ms 31620 KB Output is correct
27 Correct 40 ms 31768 KB Output is correct
28 Correct 41 ms 31716 KB Output is correct
29 Correct 49 ms 31708 KB Output is correct
30 Correct 46 ms 31692 KB Output is correct
31 Correct 39 ms 31760 KB Output is correct
32 Correct 40 ms 31668 KB Output is correct
33 Correct 40 ms 31656 KB Output is correct
34 Correct 41 ms 31600 KB Output is correct
35 Correct 29 ms 1612 KB Output is correct
36 Correct 67 ms 32624 KB Output is correct
37 Correct 66 ms 32704 KB Output is correct
38 Correct 66 ms 32692 KB Output is correct
39 Correct 86 ms 32652 KB Output is correct
40 Correct 74 ms 33212 KB Output is correct
41 Correct 69 ms 33092 KB Output is correct
42 Correct 63 ms 33020 KB Output is correct
43 Correct 64 ms 33092 KB Output is correct
44 Correct 64 ms 33020 KB Output is correct
45 Correct 90 ms 33152 KB Output is correct
46 Correct 69 ms 32700 KB Output is correct
47 Correct 72 ms 33236 KB Output is correct
48 Correct 72 ms 33196 KB Output is correct
49 Correct 73 ms 33064 KB Output is correct
50 Correct 68 ms 32836 KB Output is correct