Submission #673707

#	Time	Username	Problem	Language	Result	Execution time	Memory
673707		asteilind	Knapsack (NOI18_knapsack)	C++17	73 / 100	1085 ms	3916 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;
    vector<ll> price(n),weight(n),count(n);
    forn(i,n)
    {
        cin >> price[i] >> weight[i] >> count[i];
        ll maxv = s/(weight[i]);
        count[i] = min(count[i],maxv);
    }
    vector<ll> dp(s+1,-1);
    dp[0] = 0;
    ll res = 0;
    for (ll a=0 ; n>a ; a++)
    {
        for (ll j = 0 ; count[a] > j ; j++)
        {
            for (ll i=s ; i >= 0; i--)
            {
                if (dp[i] != -1)
                {
                    if (i+weight[a] > s) continue;
                    dp[i+weight[a]] = max(dp[i+weight[a]],dp[i]+price[a]);
                    res = max(res,dp[i+weight[a]]);
                }
            }
        }
    }
    cout << res << endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    setIO();
    solve();
}

Compilation message (stderr)

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: 0 / 27