Submission #517018

#	Time	Username	Problem	Language	Result	Execution time	Memory
517018		DiTenix	Knapsack (NOI18_knapsack)	C++17	100 / 100	97 ms	35136 KiB

knapsack

#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define sz(x) int((x).size())
#define ALL(x) (x).begin(),(x).end()
#define ln cout << '\n'
#define REP(i, a) for (int i = 0; i < int(a); i++)
#define FOR(i, a) for (int i = 1; i <= int(a); i++)
#define MEM(a,b) memset((a),(b),sizeof(a))
const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
using namespace std;
#include <bits/stdc++.h>
using ll = long long;
using vi = vector<int>;
template<typename T> void rd(vector<T> &a) {for (auto &ele : a) cin >> ele;}
template<typename T> void writeln(vector<T> &a) {for (auto &ele : a) cout << ele << ' '; cout << "\n";}
#if __cplusplus > 201402L
template<typename... Args> void rd(Args&... args) {((cin >> args), ...);}
template<typename... Args> void write(Args... args) {((cout << args << " "), ...);}
template<typename... Args> void writeln(Args... args) {((cout << args << " "), ...); cout << "\n";}
#endif
const int maxn = 1e6 + 5;

ll v[maxn], w[maxn], k[maxn];
ll dp[2005][2005];
struct item {
    int v, k;
};
vector<item> b[2005];
signed main()
{

    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
//    int t;cin >> t;while(t--) solve();
    int n, S;
    cin >> S >> n;
    FOR(i, n) {
        int v, w, k;
        rd(v, w, k);
        b[w].pb({v, k});
    }
    REP(i, 2005) REP(j, 2005) dp[i][j] = -INF;
    dp[0][0] = 0;
    int at = 0;
    for (int w = 1; w <= S; ++w) {
        if (b[w].empty()) continue;
        at++;
        sort(ALL(b[w]), [](item & a, item & b) {
            return a.v > b.v;
        });
        auto& items = b[w];
        for (int i = 0; i <= S; ++i) {
            dp[at][i] = dp[at - 1][i];
            int copy = 0;
            int type_at = 0;
            int curr_used = 0;
            ll value = 0;
            while ((copy + 1) * w <= i && type_at < sz(items)) {
                copy++;
                value += items[type_at].v;

                if (dp[at - 1][i - copy * w] != - INF) {
                    dp[at][i] = max(
                                    dp[at][i],
                                    dp[at - 1][i - copy * w] + value
                                );

                }

                curr_used++;
                if (curr_used == items[type_at].k) {
                    curr_used = 0;
                    type_at++;
                }
            }
        }
    }
    ll res = 0;
    for (int i = 0; i <= S; ++i) {
        res = max(res, dp[at][i]);
    }
    writeln(res);
    return 0;
}

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