Submission #766627

#	Time	Username	Problem	Language	Result	Execution time	Memory
766627		Mathandski	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	212 KiB

knapsack

#define pb push_back
#define mt make_tuple
#define mp make_pair
#define is insert
#define ll long long
#define vl vector<ll>
#define sl set<ll>
#define msl multiset<ll>
#define pl pair<ll, ll>
#define vpl vector<pair<ll, ll>>
#define f0r(i, begin, end) for (ll i = begin; i < end; i ++) 
#define len(x) x.size()
#include "bits/stdc++.h"
using namespace std;

struct item {
    int value, weight, amount;
};
bool comp (item a, item b) {
    return (a.value * b.weight) > (b.value * a.weight);
}

vector<item> items;
bool visited[2001];
int dp[2001], S, N, ans = 0;

int main () {
    ios_base::sync_with_stdio(0); cin.tie(nullptr);
    cin >> S >> N;
    f0r (i, 0, N) {
        int a, b, c; cin >> a >> b >> c;
        items.pb({a, b, c});
    }
    sort(items.begin(), items.end(), comp);
    
    visited[0] = 1;
    for (auto i : items) {
        f0r (j, 0, i.amount) {
            bool updated = false;
            for (int k = S; k >= i.weight; k --) {
                if(visited[k - i.weight] && (!visited[k])) {
                    updated = true;
                    visited[k] = 1;
                    dp[k] = dp[k - i.weight] + i.value;
                    ans = max(ans, dp[k]);
                }
            }
            if(!updated) break;
        }
    }
    cout << ans << endl;
}

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