Submission #729221

#TimeUsernameProblemLanguageResultExecution timeMemory
729221PVSekharKnapsack (NOI18_knapsack)C++14
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const ll MOD = 1000000007; int main() { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif int n,s; cin>>s>>n; vector<int> dp(s+1,0); dp[0]=1; map<int,vector<pair<int,int>>> store; int v,w,k; for (int i = 0; i < n; i++) { cin>>v>>w>>k; store[w].push_back({v,k}); } for (int i = 0; i <= s; i++) { sort(store[i].begin(),store[i].end()); } int ind=0,x; for (int i = 1; i <= s; i++) { ind=0; if(store[i].size()==0)continue; for (int j = 0; j <= ceil(s/i); j++) { if(store[i][ind].second){ store[i][ind].second--; x=store[i][ind].first; }else{ ind++; if(ind<store[i].size()){ store[i][ind].second--; x=store[i][ind].first; } } if(ind>=store[i].size())break; for (int k = s; k >= 0; k--) { if(dp[k]&&i+k<=s)dp[i+k]=max(dp[i+k],dp[k]+x); } } } int ans=0; for (int i = 0; i <= s; i++) { ans=max(ans,dp[i]); } cout<<ans-1<<endl; return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                 if(ind<store[i].size()){
      |                    ~~~^~~~~~~~~~~~~~~~
knapsack.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             if(ind>=store[i].size())break;
      |                ~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen("input.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen("output.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:48:59: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |                 if(dp[k]&&i+k<=s)dp[i+k]=max(dp[i+k],dp[k]+x);
#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...