Submission #1135928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135928		ashokanr	Knapsack (NOI18_knapsack)	C++20	73 / 100	1093 ms	18556 KiB

knapsack

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int a[N],b[N],k[N];
int dp[N];
vector <int> W,V;
main()
{
    ios_base::sync_with_stdio(0);
    int n,s;
    cin >> s >> n;
    for(int i=1;i<=n;++i)
    {
        cin >> b[i] >> a[i] >> k[i];
        k[i] = min(k[i],s/a[i]);
    }
    W.push_back(0);
    V.push_back(0);
    for(int i=1;i<=n;i++)
    {
        int pw = 1;
        while (k[i] >= pw )
        {
            k[i] -= pw;
            if (a[i] * pw > s) break;
            W.push_back(a[i] * pw);
            V.push_back(b[i] * pw);
            pw *= 2;
        }
        if (k[i] > 0)
        {
            if (a[i] * k[i] > s) continue;
            W.push_back(a[i] * k[i]);
            V.push_back(b[i] * k[i]);
        }
    }
//    for(auto x:W) cout << x << " ";
//    cout << endl;
//    for(auto x:V) cout << x << " ";
    for(int i=1;i<=W.size()-1;++i)
    {
        for(int j=s;j;--j)
        {
            if (j >= W[i]) dp[j] = max(dp[j],dp[j-W[i]] + V[i]);
        }
    }
    cout << *max_element(dp,dp+s+1);


}

Compilation message (stderr)

knapsack.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main()
      | ^~~~

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