Submission #771331

#	Time	Username	Problem	Language	Result	Execution time	Memory
771331		orcslop	Knapsack (NOI18_knapsack)	C++17	100 / 100	50 ms	4948 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size() 
bool ckmin(long long& a, long long b){ return b < a ? a = b, true : false; }
bool ckmax(long long& a, long long b){ return b > a ? a = b, true : false; }

const int MAXS = 2000; 

int s, n; 
long long dp[MAXS + 1]; 
vector<pair<long long, int>> v[MAXS + 1]; 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> s >> n; 
    for(int i = 0; i < n; i++){
        long long value; 
        int weight, cnt; 
        cin >> value >> weight >> cnt; 
        if(weight <= s && cnt > 0){
            v[weight].push_back(make_pair(value, cnt)); 
        }
    }
    for(int weight = 1; weight <= s; weight++){
        sort(v[weight].begin(), v[weight].end(), [](pair<long long, int> &p1, pair<long long, int> &p2){
            return p1.first > p2.first; 
        }); 
        vector<long long> sums; 
        long long curr = 0; 
        int copies = 0, at = 0, used = 0; 
        for(int j = s; j >= 0; j--){
            if(at < sz(v[weight]) && j + (copies + 1) * weight <= s){
                curr += v[weight][at].first; 
                sums.push_back(curr); 
                copies++; 
                used++; 
                if(used == v[weight][at].second){
                    used = 0; 
                    at++; 
                }
            }

            for(int k = 0; k < copies; k++){
                ckmax(dp[j + (k + 1) * weight], dp[j] + sums[k]); 
            }
        }
        // cout << weight << '\n'; 
        // for(auto x : sums) cout << x << ' ';
        // cout << '\n' << '\n';  
    }
    // for(int i = 0; i <= s; i++) cout << dp[i] << ' '; 
    cout <<  *max_element(dp, dp + s + 1); 
    return 0; 
}

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