Submission #527380

#	Time	Username	Problem	Language	Result	Execution time	Memory
527380		boris_mihov	Knapsack (NOI18_knapsack)	C++14	0 / 100	1093 ms	332 KiB

knapsack

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <vector>
#define int long long
using namespace std;
const int maxn = 1e5 + 10, maxs = 2e3 + 10, maxlog = 12;

int n, s;
struct item { int w, v, quantity; } items[maxn];
vector < pair < int, int > > by_w[maxs];
vector < pair < int, int > > sequence;
int dp[maxlog*maxs][maxs];

int f(int ix, int taken) {

    if (ix == sequence.size()) return 0;
    if (dp[ix][taken] != -1) return dp[ix][taken];

    dp[ix][taken] = f(ix+1, taken);
    if (taken + sequence[ix].first <= s) dp[ix][taken] = max(dp[ix][taken], f(ix+1, taken + sequence[ix].first) + sequence[ix].second);

    return dp[ix][taken];

}

void solve() {

    sequence.push_back({0, 0});
    for (int i = 1 ; i <= s ; ++i) {

        if (by_w[i].empty()) continue;
        sort(by_w[i].begin(), by_w[i].end(), greater < pair < int, int > > ());
        int cnt = 0, j = 0, currcnt;
        while (j < by_w[i].size() && cnt < s/i) {

            currcnt = 0;
            while (cnt < s/i && currcnt < by_w[i][j].second) {

                sequence.push_back({i, by_w[i][j].first});
                ++cnt;
                ++currcnt;

            }

            ++j;

        }

    }
    
    while (true);
    memset(dp, -1, sizeof(dp));
    cout << f(1, 0) << '\n';

}

void fast_io() {

    ios_base :: sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);

}

void read() {
    
    cin >> s >> n;
    for (int i = 1 ; i <= n ; ++i) {

        cin >> items[i].v >> items[i].w >> items[i].quantity;
        if (items[i].w <= s) by_w[items[i].w].push_back({items[i].v, items[i].quantity});

    }
}

signed main () {

    // freopen("feast.in", "r", stdin);
    // freopen("feast.out", "w", stdout);

    fast_io();
    read();
    solve();

    return 0;

}

Compilation message (stderr)

knapsack.cpp: In function 'long long int f(long long int, long long int)':
knapsack.cpp:18:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if (ix == sequence.size()) return 0;
      |         ~~~^~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void solve()':
knapsack.cpp:36:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while (j < by_w[i].size() && cnt < s/i) {
      |                ~~^~~~~~~~~~~~~~~~

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