Submission #876182

#	Time	Username	Problem	Language	Result	Execution time	Memory
876182		tth	Knapsack (NOI18_knapsack)	C++17	100 / 100	53 ms	5128 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair <ll, ll>
#define foru(i,a,b) for (ll i = a; i <= b; i++)
#define ford(i,a,b) for (ll i = a; i >= b; i--)
#define N int(1e5 + 5)
#define M int(2e3 + 5)
#define MOD int(1e9 + 7)
#define base 311

int n, s;
ll dp[M];
vector <ii> w[M];

bool cmp(ii i, ii j)
{
    return i.first > j.first;
}

int main()
{
    // freopen("KNAPSACK.inp","r",stdin);
    // freopen("KNAPSACK.out","w",stdout);
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
 
    cin >> s >> n;
    foru(i, 1, n)
    {
        int v, u, k;
        cin >> v >> u >> k;
        w[u].push_back({v, k});
    }
 
    foru(i, 1, s) 
    {
        dp[i] = -1;
        sort(w[i].begin(), w[i].end(), cmp);
    }
    
    foru(i, 1, s)
    {
        int dem = 0;
        for (ii j : w[i])
        {
            if (dem > s/i) break;
            foru(z, 1, j.second)
            {
                if (dem > s/i) break;
                ford(t, s, i)
                    if (dp[t - i] != -1)
                        dp[t] = max(dp[t], dp[t-i] + j.first);
                dem++;
            }
        }
    }
    
    cout << *max_element(dp, dp+1+s);
 
    return 0;
}

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