Submission #797605

#	Time	Username	Problem	Language	Result	Execution time	Memory
797605		procodgok	Knapsack (NOI18_knapsack)	C++17	100 / 100	57 ms	4724 KiB

knapsack

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll         long long int
#define umap       unordered_map
#define mod        998244353ll
#define pb         push_back
#define all(x)     (x).begin(), (x).end()
#define rall(x)    (x).rbegin(), (x).rend()
#define MN(a,b,c)  min(a,min(b,c))
#define MX(a,b,c)  max(a,max(b,c))
#define pr1         pair<ll,ll>
#define F          first
#define S          second
#define mP         make_pair
#define f(i,n)     for(ll i=0;i<n;i++)
#define f1(i,x,y)  for(ll i=x;i<=y;i++)
#define f2(i,x,y)  for(ll i=x;i>=y;i--)
#define yes        cout<<"Yes"<<"\n"
#define no         cout<<"No"<<"\n"
#define modsum(a,b)  ((a%mod)+(b%mod))%mod
#define modpro(a,b)  ((a%mod)*(b%mod))%mod
#define moddif(a,b)  ((a%mod)-(b%mod)+mod)%mod
#define modsumt(a,b,c) modsum(a,modsum(b,c))
// Remove macro of endl in interactive task
// in case of no errors check macros and functions again
//__builtin_popcount(x)
//__builtin_parity(x)   =(number of set bits)%2
//__builtin_clz(x)      to count the number of leading  zeroes 
//__builtin_ctz(x)      to count the number of trailing zeroes 
//__gcd(a,b)
// Binary Search 
// TO AVOID GETTING INFINITE LOOP
// mid = (l+r)/2      l=mid+1   r=mid
// mid = (l+r+1)/2    l=mid     r=mid-1
//std::cout << std::fixed; std::cout << std::setprecision(12); std::cout << z ;
using namespace std;
bool cmp(pair<ll,pair<ll,ll>> a,pair<ll,pair<ll,ll>> b)
{
   if(a.F == b.F)
   {
       return a.S.F > b.S.F;
   }
   else return a.F<b.F;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll s,n;cin>>s>>n;
  vector <pair<ll,pair<ll,ll>>> v(n);
  f(i,n)
  {
     ll val,wei,freq;
     cin>>val>>wei>>freq;
     v[i]={wei,{val,freq}};
  } 
  vector <ll> dp(s+1,-1);
  dp[0]=0;
  sort(all(v),cmp);
  ll c=0;
  f(i,n)
  {
      ll wei=v[i].F;
      ll val=v[i].S.F;
      ll freq=v[i].S.S;
      ll lim = s/wei;
      if(i>0 && v[i].F==v[i-1].F)
      {
          freq=min(freq,lim-c);
          c+=freq;
      }
      else
      {
          c=freq;
          freq=min(freq,lim);
      }
      if(freq>0)
      {
            for(ll j=s;j>=0;j--)
            {
                ll c=1,VAL=val,WEI=wei;
                while(c<=freq && WEI<=j)
                {
                    if(dp[j-WEI]!=-1) dp[j]=max(dp[j],dp[j-WEI]+VAL);
                    VAL+=val;
                    WEI+=wei;
                    c++;
                }
            }
      }
  }
  ll ans=0;
  f(i,s+1) ans=max(ans,dp[i]);
  cout<<ans;
  
}

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