Submission #1060865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060865		manhlinh1501	Knapsack (NOI18_knapsack)	C++17	0 / 100	50 ms	76068 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 105;
const int MAXM = 1e5 + 5;
const int MAXV = 1e3 + 5;

#define ALL(a) (a).begin(), (a).end()

struct event {
    int w, v, x;
    event(int w = 0, int v = 0, int x = 0) : w(w), v(v), x(x) {}
};

int N, K;
event a[MAXN];
i64 dp[MAXM];
vector<int> g[MAXV];

signed main() {
#define TASK "P1"

    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }

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

    cin >> N >> K;

    for(int i = 1; i <= N; i++) {
        auto &[w, v, x] = a[i];
        cin >> w >> v >> x;
    }

    for(int i = 1; i <= N; i++) {
        auto [w, v, x] = a[i];
        for(int j = 1; j <= x; j++)
            g[w].emplace_back(v);
    }

    for(int i = 1; i < MAXV; i++) {
        sort(ALL(g[i]));
        reverse(ALL(g[i]));
        while(!g[i].empty() and  (g[i].size() - 1) * i > K)
            g[i].pop_back();
    }

    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;
    for(int i = 1; i < MAXV; i++) {
        for(int x : g[i]) {
            for(int j = K; j >= i; j--)
                dp[j] = max(dp[j], dp[j - i] + x);
        }
    }
    i64 ans = *max_element(dp, dp + K + 1);
    cout << ans;

    return (0 ^ 0);
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:48:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         while(!g[i].empty() and  (g[i].size() - 1) * i > K)
      |                                  ~~~~~~~~~~~~~~~~~~~~~~^~~
knapsack.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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