Submission #1105499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105499		themaver1cks	Knapsack (NOI18_knapsack)	C++14	100 / 100	89 ms	35176 KiB

knapsack

/**
｡∠(*・ω･)っ  ⌒ 由 ~    ((　,,・з・,,　))
 _Π_____。
/______/~＼
｜ 田田｜門｜
why im so dumb man >.<
**/
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define el "\n"

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
// var dec
const int maxn = 1e5 + 3;
int s, n;
// ds dec
map <int, vector<pii>> mp;
//
void solve()
{
    cin >> s >> n;
    for (int i=1; i<=n; ++i)
    {
        int v, w, k; cin >> v >> w >> k;
        mp[w].pb({v, k});
    }
    for (auto &x: mp)
    {
        sort(x.se.begin(), x.se.end(), [](pii x1, pii x2){
            return x1.fi > x2.fi;
        });
    }
    //
//    for (auto x: mp)
//    {
//        cout << x.fi << ":\n";
//        for (auto _x: x.se) cout << _x.fi << " " << _x.se << el;
//        cout << el;
//    }
//    cout << el;
    vector <vector<ll>> dp(sz(mp)+3, vector<ll>(s+3, 0));
    int ind = 0;
    for (auto x: mp)
    {
        ++ind;
        int w = x.fi;
        vector <pii> v = x.se;
        for (int t=1; t<=s; ++t) dp[ind][t] = dp[ind-1][t];
        for (int t=1; t<=s; ++t)
        {
            // t/w = max number of items can get
            int copies = 0, sumval = 0;
            for (int i=0; i<sz(v); ++i)
            {
                int val = v[i].fi, c = v[i].se;
                while ((copies+1) <= t/w && c)
                {
                    copies++;
                    c--;
                    sumval += val;
//                    if (ind == 2) cout << el << t << " " << copies <<  " " << dp[ind][t] << " " << sumval << " " << dp[ind-1][t-copies*w] << el;
                    if (t-copies*w >= 0) dp[ind][t] = max(dp[ind][t], dp[ind-1][t-copies*w] + sumval);
                }
                if (copies == t/w) break;
            }
//            cout << dp[ind][t] << " ";
        }
//        cout << el;
    }
    cout << dp[ind][s] << el;
}
//
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("lmao.inp", "r"))
    {
        freopen("lmao.inp", "r", stdin);
        freopen("lmao.out", "w", stdout);
    }
    int t = 1;
//    cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen("lmao.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("lmao.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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