Submission #1257742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257742		jsw	Knapsack (NOI18_knapsack)	C++20	100 / 100	42 ms	3336 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
using pl = pair<ll, ll>;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vpi = vector<pair<int,int>>;
using vpl = vector<pair<ll,ll>>;
 
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
 
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a) - 1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a) - 1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b) - 1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)

struct triple{
  ll x,y,z;
};
bool sorting(triple a, triple b){
  if(a.y!=b.y)return a.y<b.y;
  return a.x>b.x;
}

void solve(){
  ll n,s; cin>>s>>n;
  vector<triple>a(n);
  FOR(i,n)cin>>a[i].x>>a[i].y>>a[i].z;
  FOR(i,n)a[i].z=min(a[i].z,s/a[i].y);
  vl dp(s+1,0);
  sort(all(a),sorting);
  vl cnt(s+1,0);
  vector<triple>c;
  FOR(i,n){
    if(cnt[a[i].y]>=s/a[i].y)continue;
    a[i].z=min(a[i].z,s/a[i].y-cnt[a[i].y]);
    cnt[a[i].y]+=a[i].z;
    c.pb(a[i]);
  }
  n=c.size();
  FOR(i,n){
    for(int x=0; (1<<x)<c[i].z; x++){
      FOR_R(j,(1<<x)*c[i].y,s+1){
        dp[j]=max(dp[j],dp[j-(1<<x)*c[i].y]+(1<<x)*c[i].x);
      }
      c[i].z-=(1<<x);
    }
    FOR_R(j,c[i].y*c[i].z,s+1){
        dp[j]=max(dp[j],dp[j-c[i].y*c[i].z]+c[i].z*c[i].x);
    }
  }
  ll ans=0;
  FOR(i,s+1)ans=max(ans,dp[i]);
  cout<<ans<<"\n";
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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