Submission #762858

#	Time	Username	Problem	Language	Result	Execution time	Memory
762858		LeaRouse	Knapsack (NOI18_knapsack)	C++14	100 / 100	669 ms	126188 KiB

knapsack

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define ff first
#define ss second
using namespace std;
const int MAX=2e3+5;
const int INF=2e9+1;
vector<int>B;
vector<int>C;    
vector<pair<int,int>>v[MAX];
int s,n,dp[MAX*11][MAX];
int Dp(int ind,int peso){
    if(peso>s)  return -INF;
    if(ind==B.size())   return 0;
    if(dp[ind][peso]!=-INF) return dp[ind][peso];
    //lo toma
    dp[ind][peso]=max(dp[ind][peso],Dp(ind+1,peso+C[ind])+B[ind]);
    dp[ind][peso]=max(dp[ind][peso],Dp(ind+1,peso));
    return dp[ind][peso];
}

void go(){   
    cin>>s>>n;
    for(int i=0;i<n;i++){
        int a,b,c;  cin>>a>>b>>c;
        v[b].push_back({a,c});
    }
    for(int i=1;i<=s;i++){
        sort(v[i].begin(),v[i].end());
        reverse(v[i].begin(),v[i].end());
    }
    for(int i=s;i>=1;i--){
        int aux=s/i;
        for(auto it:v[i]){
            int ns=it.ss;
            while(aux!=0 and ns!=0){
                B.push_back(it.ff);
                C.push_back(i);
                aux--;
                ns--;
            } 
        }
    }
    for(int i=0;i<=B.size();i++){
        for(int j=0;j<=s;j++){
            dp[i][j]=-INF;
        }
    }
    cout<<Dp(0,0)<<endl;
}
int main(){
    fastio;
    //freopen("time.in", "r", stdin);
    //freopen("time.out", "w", stdout);
    go();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int Dp(int, int)':
knapsack.cpp:15:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if(ind==B.size())   return 0;
      |        ~~~^~~~~~~~~~
knapsack.cpp: In function 'void go()':
knapsack.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<=B.size();i++){
      |                 ~^~~~~~~~~~

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