Submission #1169443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169443		I_FloPPed21	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	324 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=200005;
long long n,s;
struct produs
{
    long long val,g,k;
}inter[N];
vector<produs>sume;
long long dp[4000];
void citeste()
{
    cin>>s>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>inter[i].val>>inter[i].g>>inter[i].k;
    }
    sort(inter+1,inter+n+1,[](produs x,produs y){return (x.val/x.g)>(y.val/y.g);});
    for(int i=1; i<=n; i++)
    {
        long long a,b,val;
        cin>>val>>a>>b;
        while(b&&a<=s&&sume.size()<=10000)
        {
            if(b%2==1)
            {
                sume.push_back({val,a,1});
                b--;
                b/=2;
                a*=2;
                val*=2;
            }
            else
            {
                sume.push_back({val,a,2});
                b-=2;
                b/=2;
                a*=2;
                val*=2;
            }
            if(a>s)
                break;
        }
    }
}
long long ans=0;
void get_dp()
{
    for(auto [val,b,c]:sume)
    {
        for(int actual=s; actual>=0; actual--)
        {
            for(int d=1; d<=c; d++)
            {
                if(actual+d*b<=s)
                {
                    dp[actual+d*b]=max(dp[actual+d*b],dp[actual]+val*d);
                }
            }
        }
    }
    for(int i=0; i<=s; i++)
        ans=max(ans,dp[i]);
    cout<<ans;

}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    citeste();
    get_dp();
    return 0;
}

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