Submission #921057

#	Time	Username	Problem	Language	Result	Execution time	Memory
921057		josiftepe	Knapsack (NOI18_knapsack)	C++14	100 / 100	120 ms	36688 KiB

knapsack

#include <iostream>
#include <map>
#include <vector>
#include <cstring>
#include <set>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 1e10;
const int maxn = 2005;
int s, n;
int v[100005], w[100005], k[100005];
vector<pair<int, int> > items[maxn];
ll dp[maxn][maxn];
ll rec(int at, int left) {
    if(left < 0) {
        return -INF;
    }
    if(at < 0) {
        return 0;
    }
    if(dp[at][left] != -1) {
        return dp[at][left];
    }
    ll res = rec(at - 1, left);
    int current_weight = 0;
    int sum_value = 0;
    for(pair<int, int> p : items[at]) {
        for(int i = 1; i <= p.second; i++) {
            current_weight += at;
            sum_value += p.first;
            if(current_weight > left) {
                break;
            }
            res = max(res, rec(at - 1, left - current_weight) + sum_value);
        }
        if(current_weight > left) {
            break;
        }
    }
    
    return dp[at][left] = res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin >> s >> n;
    for(int i = 0; i < maxn; i++) {
        for(int j = 0; j < maxn; j++) {
            dp[i][j] = -1;
        }
    }
    int max_weight = 0;
    for(int i = 0; i < n; i++) {
        cin >> v[i] >> w[i] >> k[i];
        items[w[i]].push_back(make_pair(v[i], k[i]));
        max_weight = max(max_weight, w[i]);
    }
    for(int i = 0; i <= s; i++) {
        sort(items[i].rbegin(), items[i].rend());
    }
    cout << rec(max_weight, s) << endl;
    return 0;
}

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