제출 #1169442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169442		I_FloPPed21	Knapsack (NOI18_knapsack)	C++20	73 / 100	10 ms	776 KiB

knapsack

#include <iostream>
#include <vector>
using namespace std;
long long n,s;
struct produs
{
    long long val,g,k;
};
vector<produs>sume;
long long dp[4000];
void citeste()
{
    cin>>s>>n;
    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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27