Submission #998786

#	Time	Username	Problem	Language	Result	Execution time	Memory
998786		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	60 ms	36852 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 n, S;
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;
}

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

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, 0, S) cout << dp[0][i] << " "; cout << endl;
    for (int i = 1; i <= S; i++) {
        sort(all(store[i]), greater <pii> ());

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

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

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

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

                dp[i][j + weight] = max(dp[i][j + weight], dp[i - 1][j] + val);
            }
//            cout << val << " " << weight << " " << endl;
        }

//        fu(j, 0, S) cout << dp[i][j] << " "; cout << endl;
    }

    ll res = -oo;
    fu(i, 1, S) fu(j, 1, 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:23: 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: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".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         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