oj.uz

Submission #890692

# Submission time Handle Problem Language Result Execution time Memory
890692 2023-12-21T18:36:35 Z nikhilg2121 Knapsack (NOI18_knapsack) C++17
73 / 100
 189 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;

#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second
#define mp make_pair


void solve(){
     int s,n;
     cin>>s>>n;
     vi v(n);
     vi w(n);
     vi k(n);
        fori(i,n){
            cin>>v[i]>>w[i]>>k[i];
        }
        vvi dp(n+1,vi(s+1,0));

        fori(i,n+1){
            dp[i][0] = 0;
        }
        rep(i,1,n){
            rep(j,1,s){
                int t=0;
                dp[i][j] = dp[i-1][j];
                while(t<=k[i-1] && j-t*w[i-1]>=0){
                    dp[i][j] = max( dp[i][j], dp[i-1][j-t*w[i-1]] + t*v[i-1]);
                    t++;
                }
            }
        }
        int ans=0;
        fori(i,s+1){
            ans = max(ans,dp[n][i]);
        }
        // fori(i,n+1){
        //     fori(j,s+1){
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        cout<<ans<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1224 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1224 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1112 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 2 ms 1252 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1224 KB Output is correct
14 Correct 1 ms 1112 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1112 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 2 ms 1252 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 189 ms 1236 KB Output is correct
27 Correct 1 ms 1112 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 1 ms 1220 KB Output is correct
30 Correct 3 ms 1112 KB Output is correct
31 Correct 2 ms 1116 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 1 ms 1220 KB Output is correct
34 Correct 1 ms 1116 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 1228 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1224 KB Output is correct
14 Correct 1 ms 1112 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1112 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 2 ms 1252 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 189 ms 1236 KB Output is correct
27 Correct 1 ms 1112 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 1 ms 1220 KB Output is correct
30 Correct 3 ms 1112 KB Output is correct
31 Correct 2 ms 1116 KB Output is correct
32 Correct 1 ms 1116 KB Output is correct
33 Correct 1 ms 1220 KB Output is correct
34 Correct 1 ms 1116 KB Output is correct
35 Correct 19 ms 8024 KB Output is correct
36 Runtime error 121 ms 262144 KB Execution killed with signal 9
37 Halted 0 ms 0 KB -