제출 #1183232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183232		iamhereforfun	Knapsack (NOI18_knapsack)	C++17	100 / 100	43 ms	4560 KiB

knapsack

// IamHereForFun //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(S) ((S) & -(S))

const int N = 2e3 + 5;
const int M = 2e5 + 5;
const int Q = 1e5 + 5;
const int LG = 20;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int B = 350;

int s, n;
long long dp[N], mx = 0;
priority_queue<int> val[N];

void solve()
{
    cin >> s >> n;
    for (int x = 0; x < n; x++)
    {
        int v, w, k;
        cin >> v >> w >> k;
        for (int y = 0; y < LG; y++)
        {
            if (k == 0)
                break;
            if (k < (1 << y))
            {
                val[k * w].push(k * v);
                break;
            }
            else
            {
                if ((1 << y) * w > s)
                    break;
                val[(1 << y) * w].push((1 << y) * v);
                k -= (1 << y);
            }
        }
    }
    memset(dp, 0, sizeof(dp));
    for (int x = 1; x <= s; x++)
    {
        int cnt = x;
        while (cnt <= s && !val[x].empty())
        {
            long long i = val[x].top();
            // cout << i << " " << x << "\n";
            val[x].pop();
            for (int y = s; y >= cnt; y--)
            {
                dp[y] = max(dp[y], dp[y - x] + i);
                mx = max(dp[y], mx);
            }
            cnt += x;
        }
    }
    cout << mx;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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