Submission #651029

#	Time	Username	Problem	Language	Result	Execution time	Memory
651029		Mondeus	Knapsack (NOI18_knapsack)	C++17	100 / 100	58 ms	5040 KiB

knapsack

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <deque>
using namespace std;
const int maxn = 2005;
vector<pair<long long, long long>> optimal[maxn+5];
vector<long long> item[maxn+5];
long long dp[maxn+5];
long long s,n;
void solve()
{
    cin >> s >> n;
    for(int i = 1; i <= n; i++)
    {
        long long w,v,k;
        cin >> v >> w >> k;
        if(w > s) continue;
        if(k >= 2000) k = 2000;
        optimal[w].push_back({v,k});
    }
    for(int i = 1; i <= s; i++)
        sort(optimal[i].rbegin(),optimal[i].rend());
    for(int i = 1; i <= s; i++)
    {
        int cur = 0;
        long long sum = 0;
        for(int x = 1; x <= s / i; x++)
        {
            if(cur == optimal[i].size()) break;
            sum = optimal[i][cur].first;
            optimal[i][cur].second--;
            if(optimal[i][cur].second == 0) cur++;
            item[i].push_back(sum);
        }
    }

        for(int j = 1; j <= s; j++)
        {

                for(int x = 1; s - x * j >= 0 && x <= item[j].size(); x++)
                {
                    for(int i = s; i >= j; i--)
                    {
                        dp[i] = max(dp[i], dp[i-j] + item[j][x-1]);
                       // cout << dp[i] << '\n'
                    }
                }
        }
    long long ma = 0;
    for(int i = 1; i <= s; i++)
        ma = max(ma,dp[i]);
    cout << ma;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             if(cur == optimal[i].size()) break;
      |                ~~~~^~~~~~~~~~~~~~~~~~~~
knapsack.cpp:45:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |                 for(int x = 1; s - x * j >= 0 && x <= item[j].size(); x++)
      |                                                  ~~^~~~~~~~~~~~~~~~~

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