Submission #1307289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307289		ninstroyer	Knapsack (NOI18_knapsack)	C++20	73 / 100	301 ms	327680 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int wx = 2005;

ll n,s,dp[2][wx];
vector<tuple<ll,ll>> items;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>s>>n;
    for(int i = 0; i < n; i++)
    {
        int v,we,k; cin>>v>>we>>k;
        for(int i = 0; i < min(k,2000/we); i++)
        {
            items.push_back({v,we});
        }
    }
    for(int i = 0; i < items.size(); i++)
    {
        int cur = i%2, prev = 1-cur;
        for(int j = 0; j <= s; j++)
        {
            auto [vl, w] = items[i];
            dp[cur][j] = dp[prev][j];
            if(w > j) continue;
            dp[cur][j] = max(dp[cur][j], dp[prev][j-w]+vl);
        }
    }

    cout<<dp[1-items.size()%2][s];
}

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