Submission #876084

#	Time	Username	Problem	Language	Result	Execution time	Memory
876084		tth	Knapsack (NOI18_knapsack)	C++17	73 / 100	1022 ms	41840 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N int(1e5 + 5)
#define M int(2e3 + 5)
#define MOD int(1e9 + 7)
#define base 311

ll n, m, ans;
ll w[N], v[N], a[N], in[N];
ll d[M];

typedef pair <ll, ll> ii;
vector < vector <ii> > f(M);

bool cmp(int i, int j)
{
    return w[i] < w[j];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KNAPSACK.inp","r",stdin);
    // freopen("KNAPSACK.out","w",stdout);

    for (int i = 0; i <= M-5; i++) f[i].push_back(ii(-1, 0));
    f[0][0].first = 0;

    cin >> m >> n;
    for (int i = 1; i <= n; i++) 
    {
        cin >> v[i] >> w[i] >> a[i];
        if (!w[i]) f[0].back().first += v[i] * a[i];
        in[i] = i;
    }

    sort(in+1, in+1+n, cmp);

    for (int i = 1; i <= n; i++)
    {
        if (!w[in[i]]) continue;
        for (int j = 0; j <= m; j++)
        {
            ll tmp = 0;
            while (f[j].size())
            {
                if (f[j].back().first != -1 && j + w[in[i]] <= m && f[j].back().second < a[in[i]] && f[j+w[in[i]]][0].first < f[j].back().first + v[in[i]]) 
                    f[j+w[in[i]]].push_back(ii(f[j].back().first + v[in[i]], f[j].back().second + 1));
                tmp = max(tmp, f[j].back().first);
                f[j].pop_back();
            }
            f[j].push_back(ii(tmp, 0));
        }
    }
    
    for (int i = 0; i <= m; i++) ans = max(ans, f[i].back().first);
    cout << ans;
    
    cout << '\n';
    return 0;
}
    

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