Submission #977007

#	Time	Username	Problem	Language	Result	Execution time	Memory
977007		kfhjad	Knapsack (NOI18_knapsack)	C++17	100 / 100	68 ms	39372 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int dp[2002][2002][2]; // at, used copies
int maxVal[2001];

int main()
{
    cin.tie(NULL) -> sync_with_stdio(false);
    int S, N;
    cin >> S >> N;
    vector<vector<int>> v(N, vector<int>(3)); // value, weight, items

    for (auto& i : v)
        cin >> i[0] >> i[1] >> i[2];
    
    sort(v.begin(), v.end(), [](auto& a, auto& b)
    {
        if (a[1] == b[1]) // same weight
            return a[0] > b[0];
        
        return a[1] < b[1];
    });

    int prev = -1;
    for (int i = 0; i < N; ++i)
    {
        if (v[i][1] != prev)
            for (int j = 0; j <= S; ++j)
                dp[j][v[i][1]][0] = i;

        prev = v[i][1];
    }

    int ans = 0;
    for (int i = 1; i <= S; ++i)
    {
        int best = 0;
        int att = 0;

        for (int j = 0; j < i; ++j)
        {
            int addWeight = i - j;
            int at = dp[j][addWeight][0];

            if (v[at][1] != addWeight)
                continue;

            if (v[at][2] == dp[j][addWeight][1])
            {
                if (at + 1 == N || v[at + 1][1] != addWeight)
                    continue;
                
                ++at;
            }
            
            if (maxVal[j] + v[at][0] > maxVal[i])
            {
                maxVal[i] = maxVal[j] + v[at][0];

                best = j;
                att = at;
            }
        }

        for (int a = 0; a <= S; ++a)
            dp[i][a][0] = dp[best][a][0], dp[i][a][1] = dp[best][a][1];

        if (att == dp[best][i - best][0])
            ++dp[i][i - best][1];
        else
            dp[i][i - best][0] = att, dp[i][i - best][1] = 1;

        ans = max(ans, maxVal[i]);
    }

    cout << ans << endl;

    return 0;
}

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