Submission #1135927

#TimeUsernameProblemLanguageResultExecution timeMemory
1135927ashokanrKnapsack (NOI18_knapsack)C++20
100 / 100
48 ms3568 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5+5; int dp[N]; vector <int> W,V; vector <int> v[2005]; struct mitt { int v,w,k; bool operator < (const mitt &tim) { return v > tim.v; } } a[N]; main() { ios_base::sync_with_stdio(0); int n,s; cin >> s >> n; for(int i=1;i<=n;++i) { cin >> a[i].v >> a[i].w >> a[i].k; } sort(a+1,a+1+n); W.push_back(0); V.push_back(0); for(int i=1;i<=n;i++) { while (a[i].k-- && v[a[i].w].size() <= s / a[i].w) v[a[i].w].push_back(a[i].v); } for(int w=1;w<=s;w++) { for(auto x:v[w]) { W.push_back(w); V.push_back(x); } } // for(auto x:W) cout << x << " "; // cout << endl; // for(auto x:V) cout << x << " "; for(int i=1;i<=W.size()-1;++i) { for(int j=s;j;--j) { if (j >= W[i]) dp[j] = max(dp[j],dp[j-W[i]] + V[i]); } } cout << *max_element(dp,dp+s+1); }

Compilation message (stderr)

knapsack.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main()
      | ^~~~
#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...