Submission #547134

#	Time	Username	Problem	Language	Result	Execution time	Memory
547134		htphong0909	Knapsack (NOI18_knapsack)	C++17	100 / 100	104 ms	36472 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define db long double
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

const int INF = (int)1E18;
const db inf = (db)1E100;
const int MOD = (int)1E9 + 7;

typedef pair <int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<pair<int, int>> vpii;

void File()
{
    #define file "test"
    freopen(file".in", "r", stdin);
    freopen(file".out", "w", stdout);
}

int expo(int a, int b, int mod) {int res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
int mminvprime(int a, int b) {return expo(a, b - 2, b);}
int mod_add(int a, int b, int m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
int mod_mul(int a, int b, int m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
int mod_sub(int a, int b, int m) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
int mod_div(int a, int b, int m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;}

/// ======================================================= - TEMPLATE - ======================================================= ///

bool cmp(const pii& a, const pii& b)
{
    return a.first > b.first;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int s, n;
    //File();
    cin >> s >> n;
    map <int, vpii> by_weight;
    for (int i = 1; i <= n; i++)
    {
        int value, weight, amt;
        cin >> value >> weight >> amt;
        by_weight[weight].push_back({value, amt});
    }

    vii F(sz(by_weight) + 1, vi(s + 1, INT32_MIN));
    F[0][0] = 0;
    int i = 1;
    for (auto& [w, items] : by_weight)
    {
        sort(all(items), cmp);
        for (int j = 0; j <= s; j++)
        {
            F[i][j] = F[i - 1][j];
            int type_at = 0;
            int profit = 0;
            int amt = 0;
            int amt_used = 0;
            while ((amt + 1) * w <= j && type_at < sz(items))
            {
                amt++;
                profit += items[type_at].first;
                if (F[i - 1][j - amt * w] != INT32_MIN)
                {
                    F[i][j] = max(
                        F[i][j],
                        F[i - 1][j - amt * w] + profit);
                }

                amt_used++;
                if (amt_used == items[type_at].second)
                {
                    amt_used = 0;
                    type_at++;
                }

            }
        }
        i++;
    }
    cout << *max_element(F.back().begin(), F.back().end());
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void File()':
knapsack.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen(file".in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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