Submission #876180

#	Time	Username	Problem	Language	Result	Execution time	Memory
876180		tth	Knapsack (NOI18_knapsack)	C++17	37 / 100	105 ms	262144 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 <ll> w[M];

bool cmp(int i, int j)
{
    return i > j;
}

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;
        while (k--) w[u].push_back(v);
    }
 
    foru(i, 1, s) 
    {
        dp[i] = -1;
        sort(w[i].begin(), w[i].end(), cmp);
    }
    
    foru(i, 1, s)
        foru(j, 0, min((ll)w[i].size(), s/i) - 1)
            ford(z, s, i)
                if (dp[z - i] != -1)
                    dp[z] = max(dp[z], dp[z - i] + w[i][j]);
    
    cout << *max_element(dp, dp+1+s);
 
    return 0;
}

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