Submission #1038887

#TimeUsernameProblemLanguageResultExecution timeMemory
1038887DeathIsAweKnapsack (NOI18_knapsack)C++14
0 / 100
1069 ms37288 KiB
#include <iostream> #include <algorithm> #include <vector> #include <utility> using namespace std; int dp[2001][2001]; int main() { int s, n, d1, d2, d3; cin >> s >> n; vector<vector<int>> items(2001); vector<vector<int>> unsorted(2001); for (int i=0;i<n;i++) { cin >> d1 >> d2 >> d3; for (int i=0;i<d3;i++) { unsorted[d2].push_back(d1); } } for (int i=1;i<2001;i++) { sort(unsorted[i].begin(), unsorted[i].end(), greater<int>()); d1 = 0; for (int j: unsorted[i]) { d1 += j; items[i].push_back(j); } } for (int i=0;i<2001;i++) { dp[0][i] = 0; dp[i][0] = 0; } for (int i=1;i<2001;i++) { for (int j=1;j<2001;j++) { d2 = dp[i][j-1]; d1 = 0; while (d1 < items[j].size() && (d1 + 1) * j <= i) { d2 = max(d2, dp[i - ((d1 + 1) * 2)][j-1] + items[j][d1]); } } } cout << dp[s][2000]; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             while (d1 < items[j].size() && (d1 + 1) * j <= i) {
      |                    ~~~^~~~~~~~~~~~~~~~~
#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...