Submission #1300727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300727		tredsused70	Knapsack (NOI18_knapsack)	C++20	100 / 100	37 ms	1984 KiB

knapsack

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mpr make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax = 5011, mod = 1000000007, inf = 2000010000, key = 200003, lg = 20, block = 300;
const ll infll = 4000000000000000000;
const ld eps = 1e-9;

int dp[nmax];
vector<array<int, 2>> all_items[nmax];

void solve()
{
    int capacity, n, value, weight, amount;
    cin >> capacity >> n;
    for(int i = 0; i < n; i++) {
        cin >> value >> weight >> amount;
        all_items[weight].pb({value, amount});
    }
    vector<array<int, 2>> useful_items;
    for(int i = 1; i <= capacity; i++) {
        int max_amount = capacity / i;
        int cur_amount = 0;
        sort(all(all_items[i]));
        reverse(all(all_items[i]));
        for(auto j : all_items[i]) {
            int rem = max_amount - cur_amount;
            rem = min(rem, j[1]);
            cur_amount += rem;
            for(int k = 0; k < rem; k++)
                useful_items.pb({i, j[0]});
            if(cur_amount == max_amount)
                break;
        }
    }
    for(auto item : useful_items) {
        for(int cur_capacity = capacity; cur_capacity >= item[0]; cur_capacity--)
            dp[cur_capacity] = max(dp[cur_capacity], dp[cur_capacity - item[0]] + item[1]);
    }
    cout << dp[capacity] << "\n";
    return ;
}

int main()
{
    //freopen("spainting.in","r",stdin);
    //freopen("spainting.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    srand(8713);
    //init();
    int t = 1;
    //cin >> t;
    //int t_ = t;
    //t = rdi();
    while(t--) {
        //cout << "Case #" << t_ - t << ": ";
        solve();
    }
    //flush();
    return 0;
}

/*

*/

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