Submission #490924

#	Time	Username	Problem	Language	Result	Execution time	Memory
490924		tibiCoder	Knapsack (NOI18_knapsack)	C++11	12 / 100	1078 ms	972 KiB

knapsack

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <climits>
#include <unordered_map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <unordered_set>
#include <stack>

using namespace std;

struct Object {
    int worth;
    int weight;
    int capacity;

    bool operator<(const Object& other) const {
        if (weight == other.weight) {
            return worth < other.worth;
        }
        return weight < other.weight;
    }
};

int main() {
    int maxSum, nOfObjects;
    cin >> maxSum >> nOfObjects;
    vector<Object> objects(nOfObjects);
    for (int i = 0; i < nOfObjects; ++i) {
        cin >> objects[i].worth >> objects[i].weight >> objects[i].capacity;
    }
    std::sort(objects.begin(), objects.end());
    
    vector<vector<int>> dp(nOfObjects+1, vector<int>(maxSum+1, 0));
    for (int object = 1; object <= nOfObjects; ++object) {
        for (int sum = 1; sum <= maxSum; ++sum) {
            int usingOnlyThis = min(objects[object-1].capacity, sum/objects[object-1].weight) * objects[object-1].worth;
            dp[object][sum] = usingOnlyThis;
            for (int testSum = 1; testSum <= sum; ++testSum) {
                usingOnlyThis = min(objects[object-1].capacity, (sum-testSum)/objects[object-1].weight) * objects[object-1].worth;
                dp[object][sum] = max(dp[object][sum], dp[object-1][testSum] + usingOnlyThis);
            }
        }
    }

    cout << dp[nOfObjects][maxSum] << endl;


    return 0;
}

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