Submission #975536

#	Time	Username	Problem	Language	Result	Execution time	Memory
975536		vjudge1	Knapsack (NOI18_knapsack)	C++17	49 / 100	2273 ms	262148 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
int s, n;
vector<pair<int, int> > cake[2005];
int memo[20005][2005];
vector<pair<int, int> > v;
int sizee;

int dp(int idx, int we){
    if(we < 0){
        return INT_MIN;
    }
    if(idx < 0){
        return 0;
    }
    int &res = memo[idx][we];
    if(res != -1) return res;
    auto [a,b] = v[idx];
    return res = max(dp(idx - 1, we), dp(idx - 1, we - a) + b);
}

int main(){
    memset(memo, -1, sizeof memo);
    cin >> s >> n;
    for(int i = 1; i<=n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        cake[y].push_back({x, z});
    }
    for(int i = 1; i<=2000; i++){
        sort(cake[i].rbegin(), cake[i].rend());
        int used = 2000;
        int j = 0;
        while(used != 0 && j < cake[i].size()){
            auto &[a, b] = cake[i][j];
            v.push_back({i, a});
            used--;
            b--;
            if(b == 0) j++;
        }
    }
    sizee = v.size();
    cout << dp(sizee - 1, s);
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:34:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while(used != 0 && j < cake[i].size()){
      |                            ~~^~~~~~~~~~~~~~~~

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