Submission #1038887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038887		DeathIsAwe	Knapsack (NOI18_knapsack)	C++14	0 / 100	1069 ms	37288 KiB

knapsack

#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) {
      |                    ~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27