Submission #541692

#	Time	Username	Problem	Language	Result	Execution time	Memory
541692		Aanjaney	Knapsack (NOI18_knapsack)	C++17	100 / 100	115 ms	36168 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MODA 998244353
#define pb push_back
#define sortv(v) sort(v.begin(), v.end())
#define sorta(A, N) sort(A, A + N)
#define debug(x) cerr << #x << " is " << x;
#define rep(i, a, N) for (ll i = a; i < N; i++)
#define f first
#define s second
#define uniq(v)                                       \
    {                                                 \
        sort(v.begin(), v.end());                     \
        v.erase(unique(v.begin(), v.end()), v.end()); \
    }
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
using namespace std;
void solve(ll tcase)
{
    ll S, N;
    cin >> S >> N;
    map<ll, vector<pair<ll, ll> > > uniq_weight;
    rep(i, 0, N)
    {
        ll V, W, K;
        cin >> V >> W >> K;
        uniq_weight[W].pb({V, K});
    }
    ll maxn = uniq_weight.size() + 1, maxs = S + 1;
    ll dp[maxn][maxs];
    ll ind = 1;
    rep(i, 0, maxn) rep(j, 0, maxs) dp[i][j] = -1;
    dp[0][0] = 0;
    for (auto &[w, vec] : uniq_weight)
    {
        sort(vec.begin(), vec.end(), greater<pair<ll, ll> >());
        rep(i, 0, maxs)
        {
            dp[ind][i] = dp[ind - 1][i];
            ll used = 0, j = 0, cur_used = 0, gain = 0;
            while ((used + 1) * w <= i && j < vec.size())
            {
                used++;
                gain += vec[j].f;
                if (dp[ind - 1][i - used * w] != -1)
                    dp[ind][i] = max(dp[ind][i], dp[ind - 1][i - used * w] + gain);
                cur_used++;
                if (cur_used == vec[j].s)
                    cur_used = 0, j++;
            }
        }
        ind++;
    }
    ll maxi = 0;
    rep(i, 0, maxn) rep(j, 0, maxs) maxi = max(maxi, dp[i][j]);
    cout << maxi;
}
int main()
{

    speed;
    ll t = 1;
    rep(i, 1, t + 1)
        solve(i);
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve(long long int)':
knapsack.cpp:46:45: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             while ((used + 1) * w <= i && j < vec.size())
      |                                           ~~^~~~~~~~~~~~

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