Submission #501361

#TimeUsernameProblemLanguageResultExecution timeMemory
501361ala2Knapsack (NOI18_knapsack)C++14
49 / 100
1092 ms6076 KiB
/* ID: alaa523 LANG: C++11 PROB: Fruit Feast */ #include <bits/stdc++.h> #define pb push_back #define int long long #define F first #define S second using namespace std; int n,s; int v[1001000]; int w[1001000]; int k[1000100]; vector<pair<int,int>>a; int dp[200001]; int dp2[200011]; signed main() { memset(dp,-1,sizeof dp); cin>>s>>n; for(int i=0; i<n; i++) { cin>>v[i]>>w[i]>>k[i]; k[i]=min(k[i],s); } for(int i=0; i<n; i++) { for(int j=0; j<k[i]; j++) { a.pb({v[i],w[i]}); } } dp[0]=0; int mx=0; for(int j=0; j<a.size(); j++) { for(int i=0;i<=s;i++) { if(dp[i]!=-1) { if(a[j].S+i>s) continue; dp2[a[j].S+i]=max(dp[a[j].S+i],dp[i]+a[j].F); } } for(int i=0;i<=s;i++) dp[i]=max(dp[i],dp2[i]); } for(int i=1; i<=s; i++) { // cout<<" "<<i<<" "<<dp[i]<<endl; mx=max(mx,dp[i]); } cout<<mx<<endl; } //dp[i]=the maxvalue we can reach with i weight //dp[i]=max(dp[i],dp[i-w[j]]+v[j]);

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:40:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int j=0; j<a.size(); j++)
      |                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...