Submission #987515

#	Time	Username	Problem	Language	Result	Execution time	Memory
987515		DeadlyCritic	Knapsack (NOI18_knapsack)	C++17	100 / 100	100 ms	11856 KiB

knapsack

#include <bits/stdc++.h>

 
#define scan(a, __n) for(int __ = 0; __ < __n; __++)cin >> a[__];
// #define print(a, __n) for(int ___ = 0; ___ < __n; ___++)cout << a[___] << ' '; cout << '\n';
//  #define int ll

#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

// #define fr first
// #define sc second
 
#define all(v) v.begin(), v.end()
 
// #define c0 (v<<1)
// #define c1 (c0|1)
// #define md ((l+r)/2)
 
typedef long long ll;
typedef double ld;


using namespace std;

const int mod = 1e9+7;
const int maxN = 2007;

// const int maxFac = maxN; 
// ll fac[maxFac], _fac[maxFac];

// ll po(ll b, ll p){
//     b %= mod;
//     p %= mod-1;
//     ll r = 1;
//     while(p){
//         if(p&1)r = r*b%mod;
//         p >>= 1;
//         b = b*b%mod;
//     }
//     return r;
// }

// ll choose(ll k, ll n){
//     return fac[n]*_fac[k]%mod*_fac[n-k]%mod;
// }

// ll factorial(ll n, ll k){
//     ll ret = 1;
//     for(ll i = n; i >= n-k+1; i--){
//         ret = ret*i%mod;
//     }
//     return ret;
// }

int dp[maxN];
int tmp[maxN];
vector<pair<int, int>> gp[maxN];
int s, n;
int cal[maxN][maxN];

void make(int ind){
    auto& g = gp[ind];
    sort(all(g));
    reverse(all(g));
    vector<int> w;
    int qq = s/ind+2;
    for(auto u : g){
        if(w.size() >= qq)break;
        while(w.size() < qq && u.second > 0)w.push_back(u.first), u.second--;
    }
    for(int i = 0; i < w.size(); i++){
        cal[ind][i+1] = cal[ind][i]+w[i];
    }
}

void slv(){
    cin >> s >> n;
    for(int i = 0, v, w, k; i < n; i++){
        cin >> v >> w >> k;
        k = min(k, 3000);
        gp[w].push_back({v, k});
    }
    for(int i = 1; i <= s; i++){
        make(i);
        for(int j = s; j >= 0; j--){
            for(int k = i; k <= j; k += i){
                dp[j] = max(dp[j], dp[j-k]+cal[i][k/i]);
            }
        }
    }


    cout << dp[s] << endl;
}

signed main(){
    // freopen("time.in", "r", stdin);
    // freopen("time.out", "w", stdout);

    fastIO;
    // cout << fixed << setprecision (15);


    // fac[0] = 1;
    // for(int i = 1; i < maxFac; i++)fac[i] = fac[i-1]*i%mod;
    // _fac[maxFac-1] = po(fac[maxFac-1], mod-2);
    // for(int i = maxFac-2; i >= 0; i--)_fac[i] = _fac[i+1]*(i+1)%mod;

    // w[0] = 1;
    // for(int i = 1; i < maxN; i++)w[i] = w[i-1]*p%mod;
    // _w[maxN-1] = po(w[maxN-1], mod-2);
    // for(int i = maxN-2; i >= 0; i--)_w[i] = _w[i+1]*p%mod;
    
    
    int t = 1;
    // cin >> t;
    while(t--){
        // cout << "**S" << endl;

        // cout << slv() << '\n';
        slv();
        // string s;
        // cin >> s;
        // bool x = slv();
        // cout << (x?"YES":"NO") << '\n';
    }
}       
/*

*/

Compilation message (stderr)

knapsack.cpp: In function 'void make(int)':
knapsack.cpp:68:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |         if(w.size() >= qq)break;
      |            ~~~~~~~~~^~~~~
knapsack.cpp:69:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         while(w.size() < qq && u.second > 0)w.push_back(u.first), u.second--;
      |               ~~~~~~~~~^~~~
knapsack.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 0; i < w.size(); i++){
      |                    ~~^~~~~~~~~~

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