Submission #925494

#	Time	Username	Problem	Language	Result	Execution time	Memory
925494		Youssif_Elkadi	Knapsack (NOI18_knapsack)	C++17	100 / 100	97 ms	36704 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5, inf = 1e9, mod = 998244353;
long long dp[100006][2005], s, n;
vector<pair<int, int>> arr[2005];
int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    cin >> s >> n;
    for (int i = 1; i <= n; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        arr[y].push_back({x, z});
    }
    for (int i = 1; i <= s; i++)
        for (int j = 0; j <= s; j++)
            dp[i][j] = -inf;
    for (int i = 1; i <= s; i++)
    {
        sort(arr[i].begin(), arr[i].end());
        for (int j = 0; j <= s; j++)
        {
            dp[i][j] = dp[i - 1][j];
            long long rem = j, points = 0;
            int p = arr[i].size() - 1, took = 0;
            while (p >= 0 && rem >= 0)
            {
                if (rem - i < 0)
                    break;
                rem -= i;
                points += arr[i][p].first;
                took++;
                if (arr[i][p].second == took)
                    p--, took = 0;
                dp[i][j] = max(dp[i][j], dp[i - 1][rem] + points);
            }
        }
    }
    cout << dp[s][s] << "\n";
}

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