Submission #511366

#	Time	Username	Problem	Language	Result	Execution time	Memory
511366		DragosC1	Knapsack (NOI18_knapsack)	C++17	100 / 100	70 ms	3764 KiB

knapsack

#include <iostream>
#include <algorithm>
using namespace std;

#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int S, n;

struct tripla {
    int val, weight, cnt;
};

tripla input[100001];

bool csort(tripla a, tripla b) {
    if (a.val > b.val)
        return 1;
    return 0;
}

pair<int, int> a[100001];
int l;
int need[2001];

int dp[2][2001];

const int Inf = 2e9 + 1;

int main() {
    fast
    int i, j;
    cin >> S >> n;
    for (i = 1; i <= n; i++)
        cin >> input[i].val >> input[i].weight >> input[i].cnt;
    sort(input + 1, input + n + 1, csort);
    for (i = 1; i <= S; i++)
        need[i] = S / i;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= min(need[input[i].weight], input[i].cnt); j++)
            a[++l] = {input[i].weight, input[i].val};
        j--;
        need[input[i].weight] -= j;
    }
    for (i = 0; i <= 1; i++)
        for (j = 0; j <= S; j++)
            dp[i][j] = -Inf;
    dp[0][0] = dp[1][0] = 0;
    for (i = 1; i <= l; i++)
        for (j = 1; j <= S; j++)
            if (j - a[i].first >= 0)
                dp[i % 2][j] = max(dp[1 - i % 2][j], dp[1 - i % 2][j - a[i].first] + a[i].second);
            else dp[i % 2][j] = dp[1 - i % 2][j];
    int Max = 0;
    for (i = 1; i <= S; i++)
        if (dp[l % 2][i] > Max)
            Max = dp[l % 2][i];
    cout << Max;
    return 0;
}

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