제출 #1256432

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256432		shantoroy	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	2632 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define    ll              long long
#define    endl            "\n"
#define    fast_io         ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define    pb              push_back
using      vl=vector<ll>;
#define    vvl             vector<vl>
#define    asort(v)        sort(v.begin(),v.end())
#define    dsort(v)        sort(v.rbegin(),v.rend())
#define    pll             pair<ll,ll>
#define    vpl             vector<pll> 
#define    rev(v)          reverse (v.begin(),v.end());
#define    upb(vec, val)   ((upper_bound((vec).begin(), (vec).end(), (val))) - (vec).begin())
#define    lwb(vec, val)   ((lower_bound((vec).begin(), (vec).end(), (val))) - (vec).begin())
#define    sl              set<ll> 
#define    spl             set<pll> 
#define    in              insert
#define    c1            __builtin_popcountll
const ll mod = 1e9+7;
// const ll mx = 1e6;

int main() {

     fast_io;
     ll mx,n;
     cin>>mx>>n;

     vl v(n),w(n),c(n);

     for(ll i=0;i<n;i++){
          cin>>v[i]>>w[i]>>c[i];
     }

     vl dp(mx+1,0);
     
     for(ll i=0;i<n;i++){
          for(ll j=mx;j>=w[i];j--){


               for(ll cp=1;cp<=c[i];cp++){

                    if( (cp*w[i]) > j )break;

                    dp[j]=max(dp[j],dp[j-cp*w[i]]+cp*v[i]);

               }
          }
     }

     cout<<dp[mx];
     
     return 0;
}

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