제출 #1138656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138656		sitingfake	Knapsack (NOI18_knapsack)	C++20	73 / 100	172 ms	2320 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
#define ll long long
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) ((x>>(i))&1)
#define flip(x,i) (x^(1<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
const int mod=1e9+7;
const long long linf=1e18+3;
const int inf=1e9;
const int maxarr=1e6+5;
const double pi=acos(-1);
const int dx[]={0,1,-1,0};
const int dy[]={1,0,0,-1};
const int maxn=1e5+3;
int n,S;
struct event
{
    int val;
    int w;
    int k;
};
event a[maxn];
namespace sub4
{
    ll dp[105][2005];
    void solve()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=S;j++)
            {
                dp[i][j]=dp[i-1][j];
                for(int t=1;t<=min(a[i].k,S/a[i].w);t++)
                {
                    if(j<t*a[i].w) break;
                    dp[i][j]=max(dp[i][j],dp[i-1][j-t*a[i].w]+t*a[i].val);
                }
            }
        }
        ll ans=0;
        for(int i=1;i<=S;i++) ans=max(ans,dp[n][i]);
        cout<<ans;
    }
}
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   cin>>S>>n;
   for(int i=1;i<=n;i++)
   {
       cin>>a[i].val>>a[i].w>>a[i].k;
   }
   sub4::solve();
   //execute;
}

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