Submission #72749115

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
pair<ll, vector<pair<ll, ll>>> mergeItems(vector<pair<ll, ll>> items, int removeCount, int groupSize) {
    ll removedValueSum = 0;
    while (removeCount > 0 && !items.empty()) {
        auto [value, count] = items.back();
        if (count > removeCount) {
            removedValueSum += value * removeCount;
            items.back().second -= removeCount;
            break;
        }
        removedValueSum += value * count;
        removeCount -= count;
        items.pop_back();
    }
    
    vector<pair<ll, ll>> mergedItems;
    ll currentCount = 0, currentSum = 0;
    while (!items.empty()) {
        auto [value, count] = items.back();
        items.pop_back();
        
        if (currentCount > 0) {
            if (currentCount + count < groupSize) {
                currentCount += count;
                currentSum += value * count;
                continue;
            }
            count -= groupSize - currentCount;
            currentSum += value * (groupSize - currentCount);
            mergedItems.emplace_back(currentSum, 1);
            currentCount = currentSum = 0;
        }
        

        if (count >= groupSize) {
            mergedItems.emplace_back(value * groupSize, count / groupSize);
        }
        
        currentCount = count % groupSize;
        currentSum = value * currentCount;
    }
    
    return {removedValueSum, mergedItems};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int itemTypes;
    ll capacity;
    cin >> itemTypes >> capacity;
    
  
    vector<vector<pair<ll, ll>>> weightClasses(4);
    
    for (int i = 0; i < itemTypes; i++) {
        ll weight, value, count;
        cin >> weight >> value >> count;
        weightClasses[weight].emplace_back(value, count);
    }
    

    for (int weight = 1; weight <= 3; weight++) {
        sort(weightClasses[weight].begin(), weightClasses[weight].end());
    }
    
    ll maxTotalValue = 0;

    for (int weight1Remove = 0; weight1Remove < 6; weight1Remove++) {
        auto [removedValue1, mergedItems1] = mergeItems(weightClasses[1], weight1Remove, 6);
        
        for (int weight2Remove = 0; weight2Remove < 3; weight2Remove++) {
            auto [removedValue2, mergedItems2] = mergeItems(weightClasses[2], weight2Remove, 3);
            
            for (int weight3Remove = 0; weight3Remove < 2; weight3Remove++) {
                auto [removedValue3, mergedItems3] = mergeItems(weightClasses[3], weight3Remove, 2);
                
            
                ll remainingCapacity = capacity - weight1Remove - weight2Remove * 2 - weight3Remove * 3;
                if (remainingCapacity < 0) continue;
                
                remainingCapacity /= 6; 
                ll currentValue = removedValue1 + removedValue2 + removedValue3;
                
    
                vector<pair<ll, ll>> allItems = mergedItems1;
                allItems.insert(allItems.end(), mergedItems2.begin(), mergedItems2.end());
                allItems.insert(allItems.end(), mergedItems3.begin(), mergedItems3.end());
                
                sort(allItems.begin(), allItems.end());
                
  
                while (!allItems.empty() && remainingCapacity > 0) {
                    auto [value, count] = allItems.back();
                    allItems.pop_back();
                    
                    if (count >= remainingCapacity) {
                        currentValue += value * remainingCapacity;
                        break;
                    }
                    remainingCapacity -= count;
                    currentValue += value * count;
                }
                
                maxTotalValue = max(maxTotalValue, currentValue);
            }
        }
    }
    
    cout << maxTotalValue << endl;
    return 0;
}

Submission Info

Judge Result