Submission #568312

#	Time	Username	Problem	Language	Result	Execution time	Memory
568312		NeriW	Knapsack (NOI18_knapsack)	C++17	73 / 100	120 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, int> pill;
typedef vector<pill> vpill;
typedef vector<vpill> vvpill;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
const ll inf = 1e18;
int main()
{
    //freopen("..\\io\\input.txt", "r", stdin);
    //freopen("..\\io\\output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int s, n; cin >> s >> n;
    vll k(n+1, 0);
    vll v(n+1, 0);
    vll w(n+1, 0);
    vvpll dp(n+1, vpll(s+1, {0, 0}));
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i] >> k[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int m = 0; m < w[i]; m++)
        {
            priority_queue<pll> pq;
            for(int l = 0; m+l*w[i] <= s; l++)
            {
                pq.push({dp[i-1][m+w[i]*l].first - l*v[i], l});
                while(l - pq.top().second > k[i])
                    pq.pop();
                dp[i][m+w[i]*l] = max(dp[i][m+w[i]*l], {(ll)(pq.top().first + l*v[i]), (ll)(l - pq.top().second)});
            }
        }
    }
    pll ans = {0,0};
    for(int i = 0; i <= s; i++)
    {
        ans = max(ans, dp[n][i]);
    }
    cout << ans.first << "\n";
}

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