Submission #753863

#TimeUsernameProblemLanguageResultExecution timeMemory
753863ivazivaKnapsack (NOI18_knapsack)C++14
73 / 100
252 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 100010 #define MAXM 2010 //sutra ujutru kucam ovo long long s; long long n; long long w[MAXN]; long long v[MAXN]; long long k[MAXN]; vector<pair<long long,long long>> vec; long long dp[MAXM]; int main() { ios_base::sync_with_stdio(false); ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>s>>n; for (long long i=1;i<=n;i++) cin>>v[i]>>w[i]>>k[i]; for (long long i=1;i<=n;i++) { long long br=min(s/w[i],k[i]); for (long long j=1;j<=br;j++) vec.push_back({w[i],v[i]}); } long long siz=vec.size(); sort(vec.begin(),vec.end()); long long ans=0; for (long long i=0;i<siz;i++) { long long ww=vec[i].first; long long vv=vec[i].second; for (long long j=ww;j<=s;j++) { dp[j-ww]=max(dp[j-ww],dp[j]+vv); ans=max(ans,dp[j-ww]); } } cout<<ans<<endl; }
#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...