Submission #975892

#	Time	Username	Problem	Language	Result	Execution time	Memory
975892		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	167 ms	246608 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long ull;
typedef unsigned long long int ulli;
typedef long long ll;
typedef long long int lli;
typedef long double ld;
typedef string st;
#define all(x) x.begin(), x.end()
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0);
#define pii pair<int, int>
#define psi pair<string, int>
#define F first
#define S second
#define p(a, b) pair<a, b>
#define vin vector<int>
#define v(a) vector<a>
#define pll p(ll, ll)
//------------------------------------------------------------------------------------------------------------------
#define trace(x) cout<<"> "<<#x<<" : "<<x<<endl
#define trace2(x,y) cout<<"> "<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<endl
#define trace3(x,y,z) cout<<"> "<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<" | "<<#z<<" : "<<z<<endl
#define trace4(w,x,y,z) cout<<"> "<<#w<<" : "<<w<<" | "<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<" | "<<#z<<" : "<<z<<endl
// CONSTANT
#define mod     1000000007 // 1e9+7
#define mods    998244353  // Prime
#define eps     0.000000001 // 1e-9
#define inf     2147483647 // INT_MAX
#define INF     9223372036854775807 // LLONG_MAX
//-------------------------------------------------------------------------------------------------------------------
template<typename T>
void print(pair<T, T> var) { // print pair
        cout << var.first << ' ' << var.second << endl;
}

template<typename T>
void print(vector<T> var) { // print vector
        for(auto i : var) {
                cout << i << ' ';
        } cout << endl;
}

template<typename T>
void print(vector<pair<T, T>> var) { //print vector pair
        for(auto &i : var) {
                cout << i.first << ' ' << i.second << endl;
        }
}
//---------------------------------------------------------------------------------------------------------------------------

int main(){
fastIO
//int t; cin >> t;
//  while(t--){

//  }
ll s, n; cin >> s >> n;
v(v(pll)) cat(2001);
for(int i = 0; i < n; i++){
    ll val, w, k; cin >> val >> w >> k;
    cat[w].pb({val, k});
}
v(ll) knap, beb;
for(int i = 1; i <= 2000; i++){
    if(cat[i].empty()) continue;
    sort(all(cat[i]));
    ll pos = s/i;
    while(pos > 0 && !cat[i].empty()){
        ll val = cat[i].back().F;
        // trace2(val,cap);
        knap.pb(val);
        beb.pb(i);
        pos--;
        cat[i].back().S--;
        if(cat[i].back().S == 0) cat[i].ppb();
    }
}

ll m = knap.size();
// print(knap);
// print(beb);
v(v(ll)) dp(m, v(ll)(s+1, 0));

for(int i = beb[0]; i <= s; i++){
    dp[0][i] = knap[0];
}

for(int i = 1; i < m; i++){
    for(int j = 0; j <= s; j++){
        dp[i][j] = dp[i-1][j];
        if(j >= beb[i]){
            dp[i][j] = max(dp[i][j], dp[i-1][j-beb[i]]+knap[i]);
        }
    }
}

ll ans = 0;
for(int i = 0; i <= s; i++) ans = max(ans, dp[m-1][i]);
cout << ans;
}

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