Submission #533765

#	Time	Username	Problem	Language	Result	Execution time	Memory
533765		Luucifer	Knapsack (NOI18_knapsack)	C++17	100 / 100	73 ms	4932 KiB

knapsack

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

// clang-format off
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define endl "\n"
#define pb push_back
#define sz(v) int(v.size())
#define mems(x,y) memset(x,y,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define forn(i,s,e) for(int i = s; i < (e); ++i)
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d)                                                   \
for (                                                                   \
auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second;                                               \
debug("%s : %lld ms\n ", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false)
const int M = 1e9 + 7;

template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
#ifdef LOCAL
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
#else
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { for (auto v : vec) os << v << ' ';  return os; }
#endif

template <class T> T ABS(const T &x) {return x>0? x:-x;}
ll gcd(ll n1, ll n2) {return n2==0? ABS(n1) : gcd(n2,n1%n2);}
ll lcm(ll n1, ll n2) {return n1==0 && n2==0? 0 : ABS(n1*n2)/gcd(n1,n2);}
ll ceil2(ll a, ll b) {return (a + b - 1) / b;}

template <typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template <typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
template <typename T> vector<T> sorttrunq(vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
// clang-format on

// int dx[4] = {1,-1,0,0};
// int dy[4] = {0,0,1,-1};

/*
    1. When multiplying always consider the possiblity of overflow.
*/

struct Item {
    ll v, w, k;
};

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

    map<ll, vpll> W;
    forn(i, 0, n) {
        ll v, w, k;
        cin >> v >> w >> k;
        W[w].push_back({v, k});
    }

    vl dp(s + 1, 0);
    for (auto &[w, items] : W) {
        sort(items.rbegin(), items.rend());
        for (int wt = s; wt >= 0; --wt) {
            int idx = 0, cnt = 0, currItemCnt = 0;
            ll profit = 0;
            while ((cnt + 1) * w <= wt && idx < sz(items)) {
                ++cnt;
                ++currItemCnt;
                profit += items[idx].first;
                chmax(dp[wt], dp[wt - cnt * w] + profit);
                if (currItemCnt == items[idx].second) {
                    ++idx;
                    currItemCnt = 0;
                }
            }
        }
    }

    cout << dp[s] << endl;
}

int main() {
    FASTIO
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

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