제출 #1169439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169439		I_FloPPed21	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	24980 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)
        {
            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;
            }
        }
    }
}
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