Submission #836535

#	Time	Username	Problem	Language	Result	Execution time	Memory
836535		ZeroCool	Knapsack (NOI18_knapsack)	C++14	100 / 100	108 ms	4940 KiB

knapsack

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

#define int long long
#define mp make_pair
#define pb push_back


using ll = long long;
using ld = long double;


void solve(int T);
void pre();

const int mxn = 1e6 + 5;
const int SQRT = 500;
const int LOG = 20;
const int inf = 1e18;
const int mod = 1e9 + 7;
const ld eps = 1e-9;

int32_t main(){
    pre();
    int tt = 1;
    //cin>>tt;
    for(int i = 1;i<=tt;i++)solve(i);
    return 0;
}



void pre(){
    #ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
    #endif

}

struct Item{
    int value;
    int weight;
    int count;
};  

bool operator<(Item a,Item b){
    if(a.value != b.value)return a.value < b.value;
    if(a.weight != b.weight)return a.weight < b.weight;
    return a.count < b.count;
}

void solve(int T){
    int s,n;
    cin>>s>>n;

    Item A[n];

    for(int i = 0;i<n;i++)cin>>A[i].value>>A[i].weight>>A[i].count;

    sort(A, A+n);

    vector<int> val[s+1];

    for(int i = n-1;i>=0;i--){
        while(A[i].count && val[A[i].weight].size() * A[i].weight <= s){
            val[A[i].weight].push_back(A[i].value);
            A[i].count--;
        }
    }

    int dp[2 * s + 5];

    memset(dp, 0 ,sizeof dp);

    for(int i = 1;i<=s;i++){
        for(auto p : val[i]){
            for(int k = s;k>=0;k--){
                dp[k + i] = max(dp[k+i], dp[k] + p);
            }
        }
    }

    int res = 0;

    for(int i = 0;i<=s;i++){
        res = max(res, dp[i]);
    }

    cout<<res<<endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve(long long int)':
knapsack.cpp:66:67: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   66 |         while(A[i].count && val[A[i].weight].size() * A[i].weight <= s){
      |                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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