Submission #986971

#TimeUsernameProblemLanguageResultExecution timeMemory
986971CodurrKnapsack (NOI18_knapsack)C++14
49 / 100
1070 ms472 KiB
#include "bits/stdc++.h" using namespace std; #define int long long //Avoid if time complexity very close to limit #define ll long long #define sz(x) (int)((x).size()) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define f first #define s second void setIO(string s="") { ios_base::sync_with_stdio(0); cin.tie(0); if(sz(s)) { freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } } //Imp consts const int MOD=1e9+7; const int MAXN=2e5+1; const int INF=1e18+5; const double pi=3.14159265358979323846; const double ep=1e-20; signed main() { setIO(); int S,n; cin>>S>>n; vector<int> val,pr,cnt; for(int i=0;i<n;i++) { int x,y,z; cin>>x>>y>>z; val.push_back(x); pr.push_back(y); cnt.push_back(z); } vector<int> dp(S+1,-1); dp[0]=0; if(n==1) { int ans=min(cnt[0],(S/pr[0]))*val[0]; cout<<ans; return 0; } for(int i=0;i<n;i++) { int v=val[i],p=pr[i],c=cnt[i]; for(int j=S;j>=0;j--) { for(int l=1;l<=c;l++) { if(j>=l*p&&dp[j-l*p]>=0) dp[j]=max(dp[j],dp[j-l*p]+v*l); } } } int ans=0; for(auto u:dp) ans=max(ans,u); cout<<ans; return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen((s+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...