Submission #1271793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271793		sudama_bera	Knapsack (NOI18_knapsack)	C++20	37 / 100	1097 ms	33156 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
const long long  M = 1e9+7;
//unbounded knapsack then loop from 0->k
// 0/1 knapsack i.e only use once then loop k->0
template<typename T>
using min_pq=priority_queue<T,vector<T>,greater<T>>;


//(n)C(k)=(n-1)C(k-1)+(n-1)C(k) base case if nCn==0Cn==1

// product of all divisors 
// int cnt =1  pro=(exp(pro,e+1)*(exp(exp(num,(e*(e+1))/2),cnt)))%M;
// cnt=cnt*(e+1)%(M-1);
long long inv(long long x) {
    return x <=1?x:(long long)(M-M/x)*inv(M%x)%M;
    // M=k*a+r
    
}
long long f(long long num,long long denom){
   return ((num%M)*inv(denom))%M;
}
long long exp(long long a,long long b){
    long long ans=1;
    a=a%M;
    while(b){
        if(b&1){
            ans=(ans*a)%M;
        }
        a=(a*a)%M;
        b=b>>1;
    }
    return ans%M;
}
const int MX=1e6+3;
long long  FACT[MX];
long long INV_FACT[MX];
void fact(){
    FACT[0]=1;
    for(int i=1;i<=MX;i++){
        FACT[i]=(FACT[i-1]*i)%M;
    }
}
void fact_inv(){
    /*
       inv(n!)=(n+1)*inv(n+1)*(inv(n!))
       inv(n!)=(n+1)*(inv((n+1)!))


    */ 
    INV_FACT[MX]=exp(FACT[MX],M-2);
    for(int i=MX-1;i>=0;i--){
      INV_FACT[i]=(INV_FACT[i+1]*(i+1))%M;
    }
}
// de_arangement int c=1;
// c=c*i+(i%2==0?1:-1);
// n!{sum((-1)^k)/k!}  k from 0 to n

// stars and bars *|**|** (N+K-1)CN
// x1+x2....xk=n then number of solutions xi>=0 is above

long long D[6];
void d(){
    D[0]=1;
    for(int i=1;i<=6;i++){
        D[i]=D[i-1]*i+(i%2==0?1:-1);
    }
}
// nCk=n-1Ck+n-1Ck-1
long long NCX[1001][1001];
void cal_ncx(){
    NCX[0][0]=1;
    for(int i=1;i<=1000;i++){
        NCX[i][0]=1;
    }
    NCX[1][1]=1;
    for(int i=2;i<=1000;i++){
        for(int j=1;j<=i;j++){
            NCX[i][j]=NCX[i-1][j]+NCX[i-1][j-1];
        }
    }
}
//power of p in n! 
int ff(int n,int p){
    int x=0;
    while(n){
        x+=(n/p);
        n=n/p;
    }
    return x;
}

#define f first
#define s second
const int inf=1e6+1;
const long long mod=998244353;

void solve() {
    int W,n;
    cin>>W>>n;
    vector<pair<int,int>>vec;
    for(int i=0;i<n;i++){
        int wi,vi,ki;
        cin>>vi>>wi>>ki;
       for(int j=1;j<=ki;j++) vec.push_back({wi,vi});
    }
    vector<int>dp(W+1,0);
    dp[0]=0;
    for(int i=1;i<=vec.size();i++){
        int cur_w=vec[i-1].first;
            int cur_val=vec[i-1].second;
          for(int j=W;j>=cur_w;j--){
            if(j-cur_w>=0){
                dp[j]=max(dp[j],dp[j-cur_w]+cur_val);
            }
          }
    }
    cout<<dp[W]<<endl;
}

int main(){
     //freopen("snakes.in", "r", stdin);
     //freopen("snakes.out","w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
   // cin>>t;
//     fact();
 //   fact_inv();

    while(t--){
    solve();
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'void fact()':
knapsack.cpp:41:16: warning: iteration 1000002 invokes undefined behavior [-Waggressive-loop-optimizations]
   41 |         FACT[i]=(FACT[i-1]*i)%M;
      |         ~~~~~~~^~~~~~~~~~~~~~~~
knapsack.cpp:40:18: note: within this loop
   40 |     for(int i=1;i<=MX;i++){
      |                 ~^~~~
knapsack.cpp: In function 'void d()':
knapsack.cpp:67:13: warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
   67 |         D[i]=D[i-1]*i+(i%2==0?1:-1);
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:66:18: note: within this loop
   66 |     for(int i=1;i<=6;i++){
      |                 ~^~~

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