Submission #1083533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083533		icyalmond	Knapsack (NOI18_knapsack)	C++17	100 / 100	46 ms	5024 KiB

knapsack

#include <bits/stdc++.h>
#define ii pair <int, int>
#define ll long long
#define llll pair <ll, ll>
#define ld long double
#define ull unsigned long long
#define el "\n"
#define sp " "
#define fi first
#define se second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define __lcm(a, b) (a / __gcd(a, b) * b)
#define sq(x) (x) * (x)
#define sqr(x) sqrtl(x)
#define cbr(x) cbrtl(x)
#define sz(a) (ll)(a.size())
using namespace std;

const ld PI = acos(-1); const int INFI = 1e9 + 7; const ll INFL = 2e18 + 7;

int s, n, w;
ll v, a, curval, curnum, dp[2005], ans;
vector <llll> weight[2005];

void Solve()
{
    cin >> s >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v >> w >> a;
        weight[w].pub({v, a});
    }
    for (ll i = 1; i <= s; i++)
    {
        sort(weight[i].begin(), weight[i].end(), greater <llll>());
        for (int j = s; j >= 1; j--)
        {
            int l = 0;
            curval = curnum = 0;
            for (ll k = 1; i * k <= j && l <= sz(weight[i]); k++)
            {
                if (k > curnum)
                {
                    l++;
                    if (l > sz(weight[i])) break;
                    curnum += weight[i][l - 1].se;
                }
                curval += weight[i][l - 1].fi;
                dp[j] = max(dp[j], dp[j - i * k] + curval);
                //cout << i << sp << j << sp << k << sp << dp[j] << el;
            }
            ans = max(ans, dp[j]);
        }
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);  cin.tie(NULL);  cout.tie(0);
  
    Solve();
    return 0;
}

//coded by icyalmond

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