Submission #754981

#	Time	Username	Problem	Language	Result	Execution time	Memory
754981		hieupham1103	Knapsack (NOI18_knapsack)	C++17	100 / 100	87 ms	4904 KiB

knapsack

#include<bits/stdc++.h>
#define ii pair <int,int>
#define fi first
#define se second
#define int long long
#define double long double
#define endl '\n'
#define all(x) x.begin(), x.end()
using namespace std;

struct good{
    int p,w,k;
};

good a[(int)1e5 + 10];

bool cmp(good x, good y){
    if (x.w == y.w){
        return x.p > y.p;
    }
    return x.w < y.w;
}

vector <int> sto[2010];
int dp[2010];

signed main(){
    //freopen("input.INP", "r", stdin);
    //freopen("output.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, W;
    cin >> W >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i].p >> a[i].w >> a[i].k;
    }

    sort(a + 1, a + 1 + n, cmp);

    for (int i = 1; i <= n; i++){
        while(a[i].k and sto[a[i].w].size() < W / a[i].w){
            sto[a[i].w].push_back(a[i].p);
            a[i].k--;
        }

    }
    
    // for (int w = 1; w <= W; w++){
    //     if (sto[w].size() == 0){
    //         continue;
    //     }
    //     cout << w << ": ";
    //     for (auto p: sto[w]){
    //         cout << p << " ";
    //     }
    //     cout << endl;
    // }

    // cout << endl;

    int res = 0;
    for (int w = 1; w <= W; w++){
        for (auto p: sto[w]){
            for (int s = W - w; s >= 0; s--){
                dp[s + w] = max(dp[s + w], dp[s] + p);
                res = max(res, dp[s + w]);
                // cout << w << ' ' << p << ": " << s + w << " " << dp[s + w] << endl;
            }
        }
    }

    // for (int i = 1; i <= W; i++){
    //     cout << i << ": " << dp[i] << endl;
    // }

    cout << res << endl;
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:42:45: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   42 |         while(a[i].k and sto[a[i].w].size() < W / a[i].w){
      |                          ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27