Submission #841161

#	Time	Username	Problem	Language	Result	Execution time	Memory
841161		trnthienphc2003	Knapsack (NOI18_knapsack)	C++17	100 / 100	98 ms	9944 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordt(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define forde(i, a, b) for (int i = (a), _b = (b); i > _b; --i)
#define trav(a, x) for (auto& a : x)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

using namespace std;
using namespace __gnu_pbds;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef int64_t i64;
typedef pair<int,int> _ii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
constexpr int maxn=2e5+7;
constexpr i64 oo=1e9+7;
vector <i64> val[2007];
i64 dp[2007];
i64 s, n, v, w, k;

void solve() {
    cin >> s >> n;

    fort(i, 1, n) {
        cin >> v >> w >> k;
        i64 cur = 1;
        while(cur <= k && cur * w <= s) {
            val[cur * w].push_back(cur * v);
            k -= cur; cur <<= 1;
        }

        mini(k, s / w);
        if(k * w <= s) val[k * w].push_back(k * v);
    }

    fort(max_w, 1, s) {
        sort(all(val[max_w]), greater<i64>());
        while((s / max_w) < sz(val[max_w])) val[max_w].pop_back();

        trav(cur, val[max_w]) {
            fordt(i, s, max_w) maxi(dp[i], dp[i - max_w] + cur);
        }
    }

    cout << *max_element(dp + 1, dp + 1 + s);
}

#define NAME "test."
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

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

    int t=1;
    while(t--) solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(NAME"inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(NAME"out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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