Submission #784368

#	Time	Username	Problem	Language	Result	Execution time	Memory
784368		devariaota	Knapsack (NOI18_knapsack)	C++17	0 / 100	15 ms	31836 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<pair<ll,ll>> bycost[2005];
vector<pair<ll,ll>> item;
ll val[100005],cost[100005],freq[100005];
ll memo[2005][2005];
ll idx=0;

ll dp(ll x,ll y){
  if(x==item.size()) return 0;
  if(y<=0) return 0;
  if(memo[x][y]!=-1) return memo[x][y]; 
  //lewat
  ll best=dp(x+1,y);
  //ambil
  if(y>=item[x].second){
    best=max(best,dp(x+1,y-item[x].second)+item[x].first);
  }
  return memo[x][y]=best;
}

int main(){
  int t,n;cin>>t>>n;
  for(ll i=1;i<=n;i++){
    cin>>val[i]>>cost[i]>>freq[i];
    bycost[cost[i]].push_back({val[i],freq[i]});
  }
  int tot=0;
  bool masih=true;
  for(ll j=1;j<=2000;j++){
    if(bycost[j].size()>0){
        sort(bycost[j].begin(),bycost[j].end(),greater<pair<ll,ll>>());
      for(auto nx:bycost[j]){
        for(int i=1;i<=nx.second;i++){
        tot+=j;
        item.push_back({nx.first,j});
        idx++;
          if(tot>=2000){
            break;
            masih=false;
          }
        }
        if(!masih) break;
      }
    }
    if(!masih) break;
  }
  for(auto nx:item){
    cout<<nx.first<<" "<<nx.second<<endl;
  }
  memset(memo,-1,sizeof memo);
  cout<<dp(0,t);
}

Compilation message (stderr)

knapsack.cpp: In function 'long long int dp(long long int, long long int)':
knapsack.cpp:12:7: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   if(x==item.size()) return 0;
      |      ~^~~~~~~~~~~~~

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