Submission #998812

#	Time	Username	Problem	Language	Result	Execution time	Memory
998812		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	43 ms	34652 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define BIT(n) (1ll << n)
#define GBIT(x, i) ((x >> i) & 1)
#define all(v) v.begin(), v.end()
#define eb emplace_back
#define pb push_back
#define endl '\n'

#define fu(i, l, r) for (int i = (int) (l); i <= (int) (r); i++)
#define fd(i, r, l) for (int i = (int) (r); i >= (int) (l); i--)

typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
typedef unsigned long long ull;
typedef long long ll;
typedef double dl;

const int MAXN = 4e5 + 55;
const int MOD = 1e9 + 7;
const ll oo = 1ll * MOD * MOD;

int S, n;
struct datastore {
    int v, w, k;
} a[MAXN];

void rf() {
    cin >> S >> n;
    fu(i, 1, n) cin >> a[i].v >> a[i].w >> a[i].k;
}

#define sizeRocket 2005

ll dp[sizeRocket][sizeRocket];
vector <pii> store[sizeRocket];

void solve() {
    fu(i, 1, n) store[a[i].w].eb(a[i].v, a[i].k);

    memset(dp, -63, sizeof dp);
    dp[0][0] = 0;
    fu(i, 1, S) {
        sort(all(store[i]), greater <pii> ());

        int id = 0;
        ll val = 0;
        int weight = 0;

        fu(j, 0, S) dp[i][j] = dp[i - 1][j];

        while (id < store[i].size()) {
            val += store[i][id].fi;
            weight += i;
            store[i][id].se--;

            if (weight > S) break;
            if (0 == store[i][id].se) id++;

            fu(j, 0, S) if (j + weight <= S) {
                dp[i][j + weight] = max(dp[i][j + weight], dp[i - 1][j] + val);
            } else break;
        }
//        fu(j, 0, S) cout << dp[i][j] << " "; cout << endl;
    }

    ll res = -oo;
    fu(i, 0, S) fu(j, 0, S) res = max(res, dp[i][j]);
    cout << res << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "prob"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int ntest = 1;
//    cin >> ntest;
    fu(i, 1, ntest) rf(), solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         while (id < store[i].size()) {
      |                ~~~^~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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