Submission #866497

#	Time	Username	Problem	Language	Result	Execution time	Memory
866497		parlimoos	Knapsack (NOI18_knapsack)	C++14	100 / 100	66 ms	6096 KiB

knapsack

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pp pop_back
#define cl clear
#define bg begin
#define arr(x) array<ll , x>
#define lb lower_bound
#define ub upper_bound

int s , n;
vector<arr(3)> a;
ll dp[2001];
vector<int> itms[2001];
bool ms[2001];

int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);

        cin >> s >> n;
        for(int i = 0 ; i < n ; i++){
                int v , w , k;
                cin >> v >> w >> k;
                a.pb({v , w , k});
        }
        sort(a.bg() , a.end() , [](arr(3) a , arr(3) b){
                return (a[0] > b[0]);
        });
        for(auto el : a){
                if(itms[el[1]].empty() or (int)itms[el[1]].size() <= (s / el[1])){
                        int counter = el[2];
                        while((int)itms[el[1]].size() <= (s / el[1]) and counter-- > 0){
                                itms[el[1]].pb(el[0]);
                        }
                }
        }

        ms[0] = true;
        for(int i = 1 ; i <= s ; i++){
                for(int el : itms[i]){
                        for(int j = s ; j >= i ; j--){
                                if(!ms[j - i]) continue;
                                dp[j] = max(dp[j] , dp[j - i] + el);
                                ms[j] = true;
                        }
                }
        }

        int inx = 0;
        for(int i = 1 ; i <= s ; i++){
                if(dp[i] > dp[inx]) inx = i;
        }
        cout << dp[inx];
}

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