Submission #945316

#TimeUsernameProblemLanguageResultExecution timeMemory
945316mariamp1Knapsack (NOI18_knapsack)C++14
100 / 100
139 ms125412 KiB
#include<iostream> #include<algorithm> #include<vector> #include<set> using namespace std; const int N = 2000 + 5; vector<pair<int, int> > vec[N], nw; int dp[2000 * 15][N]; int main(){ int s, n; cin >> s >> n; int val, w, r; for(int i = 1; i <= n; i++){ cin>>val>>w>>r; vec[w].push_back({val, r}); } for(int i = 1; i <= s; i++){ sort(vec[i].begin(), vec[i].end()); reverse(vec[i].begin(), vec[i].end()); int tot = s / i; for(int j = 0; j < (int)vec[i].size(); j++){ int raod = vec[i][j].second; int value = vec[i][j].first; if (raod <= tot){ for(int z = 1; z <= raod; z++){ nw.push_back({i, value}); } tot -= raod; } else { for(int z = 1; z <= tot; z++){ nw.push_back({i, value}); } tot = 0; break; } } } // dp[i][j] pirveli i cali nivti, j aris wona = maximaluri value n = nw.size(); int ans = 0; for(int i = 1; i <= n; i++){ int wona = nw[i - 1].first; int value = nw[i - 1].second; for(int j = 0; j <= s; j++){ dp[i][j] = dp[i-1][j]; if (j >= wona) dp[i][j] = max(dp[i][j], dp[i-1][j-wona]+value); ans = max(ans, dp[i][j]); } } 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...