Submission #557341

#	Time	Username	Problem	Language	Result	Execution time	Memory
557341		ShivanshJ	Knapsack (NOI18_knapsack)	C++17	73 / 100	1080 ms	54976 KiB

knapsack

                                              /*Segment tree really makes clean code look ugly :P*/
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int MAXN=2e5+5;
const int INF=1e18;
const int MOD=1e9+7;
const int MAXL=13;
const int MAXW=2e3+5;
int dp[2][MAXW];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //cout<<setprecision(6)<<fixed;
    //freopen("feast.in","r",stdin);
    //freopen("feast.out","w",stdout);
    int s,n;
    cin>>s>>n;
    vector<vector<int>>sack;
    for(int i=0;i<n;i++) {
        int v,w,k;
        cin>>v>>w>>k;
        k=min(k,s/w);
        int j=MAXL-1;
        for(j=MAXL-1;((1LL<<j)&k)==0;j--);
        int x=k-(1LL<<j)+1;
        sack.push_back({v*x,w*x});
        j--;
        while(j>=0) {
            sack.push_back({v*(1LL<<j),w*(1LL<<j)});
            j--;
        }
    }
    int curr=1;
    for(int i=0;i<sack.size();i++) {
        int nxt=(curr^1);
        for(int j=0;j<=s;j++) {
            dp[curr][j]=0;
            if(sack[i][1]<=j) {
                dp[curr][j]=max(dp[curr][j],dp[nxt][j-sack[i][1]]+sack[i][0]);
            }
            dp[curr][j]=max(dp[curr][j],dp[nxt][j]);
        }
        curr=nxt;
    }
    curr^=1;
    int ans=0;
    for(int j=0;j<=s;j++) {
        ans=max(ans,dp[curr][j]);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

knapsack.cpp:6:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    6 | const int INF=1e18;
      |               ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:31:30: warning: narrowing conversion of '(((long long int)v) * (1 << j))' from 'long long int' to 'int' [-Wnarrowing]
   31 |             sack.push_back({v*(1LL<<j),w*(1LL<<j)});
      |                             ~^~~~~~~~~
knapsack.cpp:31:30: warning: narrowing conversion of '(((long long int)v) * (1 << j))' from 'long long int' to 'int' [-Wnarrowing]
knapsack.cpp:31:41: warning: narrowing conversion of '(((long long int)w) * (1 << j))' from 'long long int' to 'int' [-Wnarrowing]
   31 |             sack.push_back({v*(1LL<<j),w*(1LL<<j)});
      |                                        ~^~~~~~~~~
knapsack.cpp:31:41: warning: narrowing conversion of '(((long long int)w) * (1 << j))' from 'long long int' to 'int' [-Wnarrowing]
knapsack.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<sack.size();i++) {
      |                 ~^~~~~~~~~~~~

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