Submission #796957

#	Time	Username	Problem	Language	Result	Execution time	Memory
796957		procodgok	Knapsack (NOI18_knapsack)	C++17	73 / 100	1083 ms	3988 KiB

knapsack

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll         long long int
#define umap       unordered_map
#define mod        1000000007ll
#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;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll n,s;
  cin>>s>>n;
  vector <ll> v(n),w(n),k(n);
  f(i,n) cin>>v[i]>>w[i]>>k[i];
  vector <ll> dp(s+1,-1);
  dp[0]=0;
  f(i,n)
  {
      ll c=min(k[i],s/w[i]);
      vector <ll> dp2(s+1,-1);
      for(ll val=c*v[i],wei=c*w[i];val>=0;val-=v[i],wei-=w[i])
      {
           for(ll ans=s;ans>=wei;ans--)
           {
               if(dp[ans-wei]!=-1) dp2[ans]=max(dp2[ans],dp[ans-wei]+val);
           }
      }
      dp=dp2;
  }
  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: 0 / 27