Submission #1227522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227522		surung9898	Knapsack (NOI18_knapsack)	C++20	100 / 100	111 ms	9288 KiB

knapsack

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <random>
#ifdef _MSC_VER
#	include <intrin.h>
#	define __builtin_popcountll __popcnt
#endif

//#include <atcoder/all>
//using namespace atcoder;
//typedef modint998244353 mint;

using namespace std;

typedef long long int lld;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<lld, lld> pll;
typedef vector<int> vi;
typedef vector<lld> vl;
typedef vector<ld> vld;
typedef vector<char> vch;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vivi;
typedef vector<vl> vlvl;
typedef vector<vch> vcvc;
typedef vector<vb> vbvb;
typedef vector<vs> vsvs;

const lld mod = 1000000000000;
const lld inf = 1LL << 56;
const int nom = 200000;

typedef struct node
{
    lld val;
    int wei;
} node;

int cmp(const node& a, const node& b)
{
    return a.wei < b.wei;
}

int main()
{
    cin.tie(NULL), cout.tie(NULL);
    ios::sync_with_stdio(false);

    int s, n, idx, mn, gt;
    lld tp, tp2, tp3, now, tp4, tp5;

    cin >> s >> n;

    vlvl vals(s + 1);
    vector<node> good;

    for (int i = 0; i < n; ++i)
    {
        cin >> tp >> tp2 >> tp3;

        now = tp3, gt = 1;
        tp4 = tp, tp5 = tp2;

        for (int j = 0; j < 13; ++j)
        {
            if (gt <= now && tp5 <= s)
            {
                vals[tp5].push_back(tp4);
                now -= gt;
            }

            gt *= 2, tp4 *= 2, tp5 *= 2;
        }

        if (now && tp2 * now <= s)
            vals[tp2 * now].push_back(tp * now);
    }

    for (int i = 1; i <= s; ++i)
        sort(vals[i].begin(), vals[i].end(), greater<lld>());

    for (int i = 1; i <= s; ++i)
    {
        mn = min((int)vals[i].size(), s / i);

        for (int j = 0; j < mn; ++j)
            good.push_back({ vals[i][j], i });
    }

    sort(good.begin(), good.end(), cmp);

    vl dp(s + 1, -1), next(s + 1);

    mn = s;
    idx = (int)good.size() - 1;

    while (idx >= 0 && good[idx].wei > s / 2)
    {
        mn = good[idx].wei;

        if (good[idx].wei <= s)
            dp[good[idx].wei] = max(dp[good[idx].wei], good[idx].val);

        idx--;
    }

    dp[0] = 0;

    for (int i = idx; i >= 0; --i)
    {
        for (int j = mn; j <= s; ++j)
            next[j] = -1;

        for (int j = mn; j <= s; ++j)
        {
            if (dp[j] == -1)
                continue;

            if (j + good[i].wei <= s)
                next[j + good[i].wei] = max(next[j + good[i].wei], dp[j] + good[i].val);

            next[j] = max(next[j], dp[j]);
        }

        for (int j = mn; j <= s; ++j)
            dp[j] = next[j];

        if (good[i].wei <= s)
            dp[good[i].wei] = max(dp[good[i].wei], good[i].val);

        mn = good[i].wei;
    }

    tp = 0;

    for (int i = 0; i <= s; ++i)
        tp = max(tp, dp[i]);

    cout << tp;

    cout << '\n';

    return 0;
}

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