제출 #499808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
499808		mewnian	Knapsack (NOI18_knapsack)	C++14	100 / 100	56 ms	7300 KiB

knapsack

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#define sze(x) (ll) x.size()
#define idx(x, a) get<x>(a)
#define LID(x) (x << 1LL)
#define RID(x) (x << 1LL) + 1LL
#define ID(x) (x + MAXN)
#define CONV(x) (x - MAXN)
#define countbit(x) __builtin_popcountll(x)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pi;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r)
{
    return uniform_int_distribution<ll>(l, r)(rng);
}

const ll MAXN = 100'003;
const ll MAXS = 2003;
const ll INF = 1e18;
const ld EPS = 1e-9;

ll n, s;
ll dp0[MAXS], dp1[MAXS];
vector<pi> a[MAXN];

void solve()
{
    fill(dp0, dp0 + s + 1, 0);
    for (ll wi = 1; wi <= s; ++wi)
    {
        if (a[wi].empty()) continue;
        sort(a[wi].begin(), a[wi].end(), greater<pi>());
        vector<ll> sumval((s / wi) + 2);
        for (ll i = 1, r = 0; i < (ll)sumval.size(); ++i)
        {
            sumval[i] = sumval[i - 1] + a[wi][r].fi * max(0LL, min(1LL, a[wi][r].se));
            --a[wi][r].se;
            while (r + 1 < (ll)a[wi].size() && a[wi][r].se == 0) ++r;
        }
        for (ll sn = 0; sn <= s; ++sn)
        {
            dp1[sn] = 0;
            for (ll i = sn, cnt = 0; i >= 0; i -= wi, ++cnt)
            {
                dp1[sn] = max(dp1[sn], dp0[i] + sumval[cnt]);
            }
        }
//        for (ll sn = 0; sn <= s; ++sn) cerr << dp1[sn] << " ";
        for (ll sn = 0; sn <= s; ++sn) dp0[sn] = dp1[sn];
//        cerr << endl;
    }
    cout << dp1[s];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef OFFLINE
    freopen("input.inp", "r", stdin);
    #endif
    cin >> s >> n;
    for (ll i = 1; i <= n; ++i)
    {
        ll vi, wi, ki; cin >> vi >> wi >> ki;
        a[wi].pb({vi, ki});
    }
    solve();
}

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