Submission #1272697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272697		zagaro	Knapsack (NOI18_knapsack)	C++20	100 / 100	52 ms	2972 KiB

knapsack

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll s, n, v, w, k, r=0, a;
    cin>>s>>n;
    vector<ll> dp(s+100, -1);
    dp[0]=0;
    vector<vector<pair<ll,ll> > > ord(s+1);
    for(int i=1;i<=n;i++){
        cin>>v>>w>>k;
        ord[w].push_back({v, k});
    }
    for(int i=1;i<=s;i++){
        if(ord[i].size() > 0){
            sort(ord[i].rbegin(), ord[i].rend());
            a = s/i;
            for(int j=0;j<ord[i].size();j++){
                if(a > 0){
                    for(int k=1;k<=min(a, ord[i][j].second);k++){
                        for(int p=s;p>=0;p--){
                            if(dp[p] != -1){
                                if(p+i <= s){
                                    dp[p+i] = max(dp[p+i], dp[p]+ord[i][j].first);
                                }
                            }
                        }
                    }
                    a -= ord[i][j].second;
                }
                if(a <= 0)break;
            }
        }
    }
    for(int i=1;i<=s;i++)r=max(r, dp[i]);
    cout<<r<<ENDL;
    return 0;
}

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