Submission #1039232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039232		vjudge1	Knapsack (NOI18_knapsack)	C++14	100 / 100	38 ms	3788 KiB

knapsack

#include<bits/stdc++.h>
#define file "D"
#define ll long long
using namespace std;
const int maxN = 2e3 + 5;
 
struct points{
    int v, k;
};
 
 
bool cmp(points a, points b){
    if (a.v != b.v)
        return a.v > b.v;
 
    return a.k > b.k;
}
 
int t, n;
int s;
ll dp[maxN];
vector< points > a[maxN];
 
void solve(){
    for (int i = 1; i <= s; ++i){
        if (!a[i].size())
            continue;
        sort(a[i].begin(), a[i].end(), cmp);
 
        int index = 0;
        for (int j = 1; j * i <= s; ++j){
            if (index == a[i].size())
                break;
 
            for (int q = s; q >= i; --q)
                dp[q] = max(dp[q], dp[q - i] + a[i][index].v);
 
            a[i][index].k-= 1;
            if (a[i][index].k == 0)
                ++index;
        }
    }
    cout << dp[s];
}
 
signed main(){
//    freopen(file".inp", "r", stdin);
//    freopen(file".out", "w", stdout);
    cin.tie(NULL)->sync_with_stdio(0);
    t = 1;
    while (t--){
        cin >> s >> n;
        for (int i = 1; i <= n; ++i){
            int v, w, k;
            cin >> v >> w >> k;
            a[w].push_back({v, k});
        }
        solve();
    }
}
 

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<points>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             if (index == a[i].size())
      |                 ~~~~~~^~~~~~~~~~~~~~

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