Submission #987511

#	Time	Username	Problem	Language	Result	Execution time	Memory
987511		DeadlyCritic	Knapsack (NOI18_knapsack)	C++17	29 / 100	198 ms	1108 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;
    for(auto u : g){
        if(w.size() >= s)break;
        while(w.size() < s && 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];
    }
}

int calcSin(int po, int lq, int rq, int ind){
    // if(ind == 15)cout << "po " << po << " | ";
    rq = min(rq, po);
    tmp[po] = dp[po];
    int ii = -1;
    for(int i = lq; i <= rq; i++){
        if(tmp[po] < dp[i]+cal[ind][(po-i)/ind]){
            tmp[po] = dp[i]+cal[ind][(po-i)/ind];
            ii = i;
        }
    }
    // if(ind == 15)cout << ii << endl;
    return ii;
}
void calcTmp2(int l, int r, int lq, int rq, int ind){
    // for(int i = l; i <= r; i++)calcSin(i, lq, rq, ind);
}

void calcTmp(int l, int r, int lq, int rq, int ind){
    // for(int i = l; i <= r; i++)calcSin(i, lq, rq, ind);
    rq = min(r, rq);
    if(r < l)return;
    if(l == r){
        calcSin(l, lq, rq, ind);
        return;
    }
    int md = (l+r)>>1;
    int xx = calcSin(md, lq, rq, ind);
    calcTmp(l, md-1, lq, xx, ind);
    calcTmp(md+1, r, xx, rq, ind);
            // l <= j
            //c[l][j] = cal[i][j-l];
}

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);
        calcTmp(0, s, 0, s, i);
        // cout << endl;
        // cout << i << " :\n";
        // for(int j = 0; j <= s; j++)cout << tmp[j] << ' ';
        // cout << endl;
        // calcTmp2(0, s, 0, s, i);
        // for(int j = 0; j <= s; j++)cout << tmp[j] << ' ';
        // cout << endl;
        // cout << endl;
        for(int j = 0; j <= s; j++)dp[j] = tmp[j];
    }


    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:67:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |         if(w.size() >= s)break;
      |            ~~~~~~~~~^~~~
knapsack.cpp:68:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |         while(w.size() < s && u.second > 0)w.push_back(u.first), u.second--;
      |               ~~~~~~~~~^~~
knapsack.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < w.size(); i++){
      |                    ~~^~~~~~~~~~

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