Submission #527383

#	Time	Username	Problem	Language	Result	Execution time	Memory
527383		boris_mihov	Knapsack (NOI18_knapsack)	C++14	100 / 100	83 ms	7472 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[2][maxs];

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;

        }

    }
    
    for (int ix = sequence.size()-1 ; ix >= 1 ; --ix)
        for (int taken = 0 ; taken <= s ; ++taken) {
        
            dp[ix&1][taken] = dp[(ix+1)&1][taken];
            if (taken + sequence[ix].first <= s) dp[ix&1][taken] = max(dp[ix&1][taken], dp[(ix+1)&1][taken + sequence[ix].first] + sequence[ix].second);
        
        }


    cout << dp[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 'void solve()':
knapsack.cpp:24: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]
   24 |         while (j < by_w[i].size() && cnt < s/i) {
      |                ~~^~~~~~~~~~~~~~~~

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