Submission #1065981

#TimeUsernameProblemLanguageResultExecution timeMemory
1065981KALARRYKnapsack (NOI18_knapsack)C++14
100 / 100
46 ms3676 KiB
//chockolateman #include<bits/stdc++.h> using namespace std; int N,S,dp[2005]; //max val with space i vector<pair<int,int>> items[2005]; int main() { scanf("%d%d",&S,&N); for(int v,w,k,i = 1 ; i <= N ; i++) { scanf("%d%d%d",&v,&w,&k); items[w].push_back({v,k}); } for(int i = 1 ; i <= S ; i++) { sort(items[i].begin(),items[i].end(),greater<pair<int,int>>()); int space_taking = 0; for(auto e : items[i]) { int v = e.first; int w = i; int k = e.second; for(int x = 1 ; space_taking <= S && x <= k ; x++) { space_taking += w; if(space_taking <= S) { for(int j = S ; j >= w ; j--) dp[j] = max(dp[j],dp[j-w] + v); } } } } printf("%d\n",dp[S]); return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d%d",&S,&N);
      |     ~~~~~^~~~~~~~~~~~~~
knapsack.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d%d%d",&v,&w,&k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
#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...