Submission #634737

#	Time	Username	Problem	Language	Result	Execution time	Memory
634737		Wael	Knapsack (NOI18_knapsack)	C++14	100 / 100	127 ms	42324 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define F first
#define S second
#define endl '\n'
int const M = 2e3 + 10 , mod = 1e9 + 7;
ll n , T , Q , ans , W , val , w , c , dp[M][M] , ben[M][M];
vector<pair<ll , ll>>elem[M];

main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);

    cin >> W >> n;
    for(int i = 1 ; i <= n ; ++i) {
        cin >> val >> w >> c;
        elem[w].push_back({val , c});
    }

    for(int w = 1 ; w <= W ; ++w) {
        sort(elem[w].begin() , elem[w].end());
        int Can = W / w , rem = 0 , val = 0;
        for(int cnt = 1 ; cnt <= Can ; ++cnt) {
            if(!rem) {
                if(!elem[w].size()) break;
                rem = elem[w].back().S;
                val = elem[w].back().F;
                elem[w].pop_back();
                //cout << "val " << val << endl;
            }
            --rem;
            ben[w][cnt] = ben[w][cnt - 1] + val;
        }
    }

    for(int w = 1 ; w <= W ; ++w) { //cout << "w = " << w << endl;
        int Can = W / w;
        for(int cnt = 0 ; cnt <= Can ; ++cnt) {
            for(int have = 0 ; have <= W ; ++have) {
                dp[w][have] = max(dp[w][have] , dp[w - 1][have]);
                if(have - cnt * w < 0) continue;
                //cout << " cnt = " << cnt << " " << ben[w][cnt] << endl;
                dp[w][have] = max(dp[w][have] , dp[w - 1][have - w * cnt] + ben[w][cnt]);
                ans = max(ans , dp[w][have]);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

knapsack.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main() {
      | ^~~~

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