제출 #1257740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257740		jsw	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	2784 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__)

void solve(){
  ll n,s; cin>>s>>n;
  ll a[n][3];
  FOR(i,n)cin>>a[i][0]>>a[i][1]>>a[i][2];
  FOR(i,n)a[i][2]=min(a[i][2],s/a[i][1]);
  vl dp(s+1,0);
  FOR(i,n){
    for(int x=0; (1<<x)<a[i][2]; x++){
      FOR_R(j,(1<<x)*a[i][1],s+1){
        dp[j]=max(dp[j],dp[j-(1<<x)*a[i][1]]+(1<<x)*a[i][0]);
      }
      a[i][2]-=(1<<x);
    }
    FOR_R(j,a[i][2]*a[i][1],s+1){
        dp[j]=max(dp[j],dp[j-a[i][2]*a[i][1]]+a[i][2]*a[i][0]);
    }
  }
  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: 0 / 27