Submission #673719

#	Time	Username	Problem	Language	Result	Execution time	Memory
673719		asteilind	Knapsack (NOI18_knapsack)	C++17	100 / 100	134 ms	5032 KiB

knapsack

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <set>
#include <numeric>
#include <bitset>
#include <climits>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define ll long long
#define MOD 1000000007
using namespace std;
void setIO(string name = "") { // name is nonempty for USACO file I/O
    ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output
    if(name.length()){
        freopen((name+".in").c_str(), "r", stdin); // see Input & Output
        freopen((name+".out").c_str(), "w", stdout);
    }
}
void solve()
{
    ll s,n; cin >> s >> n;
    map<ll,vector<pair<ll,ll>>> map;
    forn(i,n)
    {
        ll p,w,c; cin >> p >> w >> c;
        map[w].push_back({p,c});
    }
    vector<ll> dp(s+1,-1);
    dp[0] = 0;
    ll res = 0;
    for (auto &[w,items]: map)
    {
        sort(items.begin(),items.end(),greater<pair<ll,ll>>());
        ll ct2 = 0;
        ll maxv = s/w;
        for (ll j=0 ; items.size()>j ; j++)
        {
            if (ct2 == maxv) break;
            for (ll i = 0; items[j].second>i && (ct2 != maxv) ; i++)
            {
                ct2++;
                for (ll a=s; a>=0 ; a--)
                {
                    if (a+w > s || dp[a] == -1) continue;
                    dp[a+w] = max(dp[a+w],(dp[a]+items[j].first));
                    res = max(res,dp[a+w]);
                }
            }
        }
    }
    cout << res << endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    setIO();
    solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:44:35: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |         for (ll j=0 ; items.size()>j ; j++)
      |                       ~~~~~~~~~~~~^~
knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen((name+".in").c_str(), "r", stdin); // see Input & Output
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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