Submission #699557

#	Time	Username	Problem	Language	Result	Execution time	Memory
699557		tmarcinkevicius	Knapsack (NOI18_knapsack)	C++14	100 / 100	206 ms	247656 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define int int64_t
typedef pair<int, int> pii;
#define f first
#define s second
#define all(a) a.begin(), a.end()
#define beg 1e18

int32_t main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int S, N; cin >> S >> N;

    vector<pii> item[S + 1];
    for (int i = 0; i < N; i++)
    {
        int V, W, K; cin >> V >> W >> K;
        item[W].push_back({V, K});
    }
    vector<pii> good;
    for (int i = 1; i <= S; i++)
    {
        sort(all(item[i]), greater<pii>());
        int cnt = S / i;
        int index = 0;
        while (index < item[i].size() && cnt > 0)
        {
            if (item[i][index].s == 0)
            {
                index++;
                continue;
            }
            item[i][index].s--;
            good.push_back({i, item[i][index].f});
            cnt--;
        }
    }
    // for (pii p : good)
    // {
    //     cout << "{" << p.f << " " << p.s << "}" << '\n';
    // }
    int dp[good.size() + 1][S + 1];
    //dp[0][0] = 0;
    for (int i = 0; i <= S; i++)
    {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= good.size(); i++)
    {
        for (int j = 0; j <= S; j++)
        {
            if (j > 0)
            {
                //cout << "(" << dp[i][j - 1] << ")\n";
                dp[i][j] = dp[i][j - 1];
            }
            else dp[i][j] = 0;
            if (j < good[i - 1].f)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            }
            else  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - good[i - 1].f] + good[i - 1].s);
            // if (dp[i][j] < -1e9) cout << "-  ";
            // else
            // {
            //     cout << dp[i][j] << " ";
            //     if (dp[i][j] < 10) cout << " ";
            // }
        }
        //cout << '\n';
    }
    cout << dp[good.size()][S];
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         while (index < item[i].size() && cnt > 0)
      |                ~~~~~~^~~~~~~~~~~~~~~~
knapsack.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 1; i <= good.size(); i++)
      |                     ~~^~~~~~~~~~~~~~

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