Submission #521554

#	Time	Username	Problem	Language	Result	Execution time	Memory
521554		AmirElarbi	Knapsack (NOI18_knapsack)	C++14	100 / 100	90 ms	34960 KiB

knapsack

#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll unsigned long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9+7;
const int nax = 2005;
ll dp[nax][nax];
vii w[nax];
int main(){ 
    optimise;
    int n,s;
    cin >> s >> n;
    for (int i = 0; i < n; ++i)
    {
        int a,b,c;
        cin >> a >> b >> c;
        w[b].pb({a,c});
    }
    dp[0][0] = 0;
    int cnt = 1;
    for (int i = 0; i <= s; ++i)
    {
        if(w[i].size()!=0){
            sort(w[i].begin(), w[i].end(), greater<ii>());
            for (int j = 0; j <= s; ++j)
            {
                dp[cnt][j] = dp[cnt-1][j];
                int c = 0,curi = 0,smv = 0,cusd = 0;
                while(((c+1)*i) <= j && curi < w[i].size()){
                    c++,
                    smv += w[i][curi].fi;
                    dp[cnt][j] = max(dp[cnt][j],dp[cnt-1][j-c*i]+smv);
                    cusd++;
                    if(cusd == w[i][curi].se){
                        curi++;
                        cusd = 0;
                    }
                }
            }
            cnt++;
        }
    }
    ll mx = 0;
    for (int j = 0; j <= s; ++j)
    {
        mx = max(mx,dp[cnt-1][j]);
    }
    cout << mx << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:46:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |                 while(((c+1)*i) <= j && curi < w[i].size()){
      |                                         ~~~~~^~~~~~~~~~~~~

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