Submission #1138659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138659		sitingfake	Knapsack (NOI18_knapsack)	C++20	100 / 100	56 ms	2892 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;
    }
}
vector<ii>W[2002];
ll dp[2020];
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;
       W[a[i].w].push_back(ii(a[i].val,a[i].k));
   }
   for(int i=1;i<=S;i++)
   {
       if(W[i].empty()) continue;
       sort(all(W[i]),greater<ii>());
       int id=0;
       for(int t=1;t*i<=S;t++)
       {
           if(id==W[i].size()) break;
           for(int j=S;j>=i;j--)
           {
               dp[j]=max(dp[j],dp[j-i]+W[i][id].fi*1ll);
           }
           W[i][id].se--;
           if(W[i][id].se==0)++id;
       }
   }
   cout<<dp[S];
   //execute;
}

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