Submission #592085

#	Time	Username	Problem	Language	Result	Execution time	Memory
592085		NintsiChkhaidze	Knapsack (NOI18_knapsack)	C++14	100 / 100	80 ms	5016 KiB

knapsack

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define s second
#define f first
#define int ll
using namespace std;

const int N = 100005;
vector <pair<int,int> > vec[2005];
int dp[N],DP[N],ans;
vector <pair<int,int> > d;

signed main() {
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int S,n;
    cin>>S>>n;
    
    for (int i = 1; i <= n; i++){
        int v,w,q;
        cin>>v>>w>>q;
        vec[w].pb({v,q});
    }
    
    for (int i = 1; i <= S; i++){
        sort(vec[i].begin(),vec[i].end());
        reverse(vec[i].begin(),vec[i].end());
        
        int sumv = 0,sumw = 0;
        d.clear();
        for (int j = 0; j < vec[i].size(); j++){
            while (sumw < S && vec[i][j].s){
                sumw += i;
                sumv += vec[i][j].f;
                d.pb({sumw,sumv});
                vec[i][j].s--;
            }
        }
        
        for (int j=0;j<d.size();j++)
            for (int p = 0; p + d[j].f <= S; p++)
                dp[p+d[j].f]=max(dp[p+d[j].f],DP[p] + d[j].s);
        
        for (int j=0;j<=S;j++){
            DP[j] = max(dp[j],DP[j]);
            dp[j]=0;
            ans=max(ans,DP[j]);
        }
    }
    
    cout<<ans;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:31:27: 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]
   31 |         for (int j = 0; j < vec[i].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~
knapsack.cpp:40:23: 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]
   40 |         for (int j=0;j<d.size();j++)
      |                      ~^~~~~~~~~

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