Submission #1104973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104973		The_Eureka	Knapsack (NOI18_knapsack)	C++17	100 / 100	652 ms	20672 KiB

knapsack

#pragma GCC optimize("Ofast","unroll-all-loops","fast-math","no-stack-protector")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define alls(x) x.begin(), x.end()
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define rep(i, n) for (int i = 1; i <= int(n); i++)
#define sz(x) int(x.size())
#define dbg(x) cerr << #x << " = " << x << endl;
#define cin std::cin
#define cout std::cout
#define pii pair<int, int>
#define pll pair<ll, ll>ip
const ld eps = 1e-12;
const ll inf = 1e16;
const ll mod = 998244353;
const ll mod1 = 1e9 + 87;
const ll mod2 = 1e9 + 93;
using namespace std;
 
void IOS(string name = "") {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false); // see /general/fast-io
    if (sz(name)) {
        freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
 
struct node {
    int w;
    ll v;
};
 
int main() {
    IOS();
    int n, W;
    cin >> W >> n;
    vector<node> objects;
    rep(i, n) {
        int v, w, m;
        cin >> v >> w >> m;
        int c = 1;
        while (m > c) {
            m -= c;
            if (1ll * w * c <= W) {
                objects.pb((node){w * c, 1ll * v * c});
            }
            c *= 2;
        }
        if (1ll * w * m <= W) {
            objects.pb((node){w * m, 1ll * v * m});
        }
    }
    vector<ll> dp(W + 1, 0);
    for (auto [w, v]: objects) {
        for (int j = W; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    cout << dp[W] << endl;
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void IOS(std::string)':
knapsack.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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