Submission #1169466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169466		Kodik	Knapsack (NOI18_knapsack)	C++17	100 / 100	65 ms	34376 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ss second
#define ff first
typedef long long ll;
typedef long double ld;
#define int ll
using pi = array<ll, 2>;
const int MOD = 1e9+7;



struct DSU{
    private:
        vector<int> parents, sizes;
    public:
    void init(int n){
        parents.resize(n); iota(parents.begin(), parents.end(), 0);
        sizes.resize(n, 1);
    }
    int find(int x){return parents[x]==x?x:(parents[x]=find(parents[x]));}
    bool unite(int a, int b){
        int root_a = find(a);
        int root_b = find(b);
        if(root_a==root_b) return false;
        if(sizes[root_a]<sizes[root_b]) swap(root_a, root_b);
        sizes[root_a] += sizes[root_b];
        parents[root_b] = root_a;
        return true;
    }
};

// max sum robime 
class SegTree{
    private:
        struct item{
            int pref = 0;
            int suff = 0;
            int sum = 0;
            int most = 0;
        };
        int n;
        vector<item> values;
        item merge(item a, item b){
            int pref = max(a.pref, a.sum+b.pref);
            int suff = max(b.suff, b.sum+a.suff);
            int sum = a.sum+b.sum;
            int most = max({a.most, b.most, a.suff+b.pref});
            return {pref, suff, sum, most};
        }
        item solo(int v){
            if(v>0){
                return {v,v,v,v};
            }
            return {0,0,v,0};
        }
        void pset(int idx, int v){
            values[idx+=n] = solo(v);
            for(idx/=2; idx > 0; idx>>=1) 
                values[idx] = merge(values[2*idx], values[2*idx+1]);
        }
        item pget(int l, int r){
            item right, left; 
            for(l+=n, r+=n; l<r; l>>=1, r>>=1){
                if (l & 1) left = merge(left, values[l++]);
                if (r & 1) right = merge(values[--r], right);
            }
            return merge(left, right);
        }
    public:
        void init(int n){
            this->n = n;
            values.resize(2*n);
        }
        void set(int idx, int v){
            pset(idx, v);
        }
        int get(int l, int r){
            return pget(l, r).most;
        }
};


int lis(vector<int> a){
    vector<int> arr;
    for(int i = 0; i < a.size(); ++i){
        int pos = upper_bound(arr.begin(), arr.end(), a[i]) - arr.begin();
        if(pos==arr.size()){
            arr.push_back(a[i]);
        }else{
            arr[pos] = a[i];
        }
    }
    return arr.size();
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int limit, number;
    cin >> limit >> number;
    map<int, vector<pair<int,int>>> by_weight;
    for (int t = 0; t < number; t++) {
		int value;
		int weight;
		int amt;
		cin >> value >> weight >> amt;
		if (weight <= limit && amt > 0) { by_weight[weight].push_back({value, amt}); }
	}

	vector<vector<int>> best(by_weight.size() + 1, vector<int>(limit + 1, INT32_MIN));
    best[0][0] = 0;
	int at = 1;
    for(auto &[w, items] : by_weight) {
		sort(items.rbegin(), items.rend());
		for (int i = 0; i <= limit; i++) {
			best[at][i] = best[at - 1][i];
			int copies = 0;
			int type_at = 0;
			int curr_used = 0;
			int profit = 0;
			while ((copies + 1) * w <= i && type_at < items.size()) {
				copies++;
				profit += items[type_at].first;
				if(best[at - 1][i - copies * w] != INT32_MIN) {
					best[at][i] =
					    max(best[at][i], best[at - 1][i - copies * w] + profit);
				}

				curr_used++;
				if (curr_used == items[type_at].second) {
					curr_used = 0;
					type_at++;
				}
			}
		}
		at++;
	}
    cout << *max_element(best.back().begin(), best.back().end()) << '\n';
    return 0;
}

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