Submission #1109725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109725		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	55 ms	3664 KiB

knapsack

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

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

// ============ Macros starts here ============
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif // DEBUG
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(Ostream& os, const Cont& v) {
    os << "[";
    for (auto& x : v) { os << x << ", "; }
    return os << "]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
    return os << "{" << p.first << ", " << p.second << "}";
}

#define readFast                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#ifdef LOCAL
#define read() ifstream fin("date.in.txt")
#else
#define read() readFast
#endif // LOCAL
// ============ Macros ends here ============

#define fin cin
#define ll long long
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define output(x) (((int)(x) && cout << "YES\n") || cout << "NO\n")
#define LSB(x) (x & (-x))
#define test cout << "WORKS\n";

const int N = 500 + 15;
const int MOD = 1e9 + 7;

int n, s;
vector<vector<pair<int, int>>> w;

int main() {
    read();
    fin >> s >> n;
    w.resize(s + 1);
    for (int i = 0; i < n; ++i) {
        int weight, val, k;
        fin >> val >> weight >> k;

        w[weight].push_back({ val, min(k, (s + weight - 1) / weight) });
    }

    for (int i = 1; i <= s; ++i) {
        sort(all(w[i]), greater<pair<int, int>>());
        int sum_nr_elements = 0;
        int limit = (s + i - 1) / i;
        for (int j = 0; j < w[i].size(); ++j) {
            if (sum_nr_elements + w[i][j].second > limit) {
                w[i][j].second = limit - sum_nr_elements;
                w[i].erase(w[i].begin() + j + 1, w[i].end());
            } else {
                sum_nr_elements += w[i][j].second;
            }
        }
    }

    vector<ll> val(s + 1, 0);
    for (int weight = 1; weight <= s; ++weight) {
        for (int i = 0; i < w[weight].size(); ++i) {
            for (int times = 1; times <= w[weight][i].second; ++times) {
                for (int j = s - weight; j >= 0; --j) {
                    if (val[j + weight] < val[j] + w[weight][i].first) {
                        val[j + weight] = val[j] + w[weight][i].first;
                    }
                }
            }
        }
    }
    cout << *max_element(all(val));

    return 0;
} /*stuff you should look for !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   * test the solution with the given example
   * int overflow, array bounds, matrix bounds
   * special cases (n=1?)
   * do smth instead of nothing and stay organized
   * WRITE STUFF DOWN
   * DON'T GET STUCK ON ONE APPROACH
~Benq~*/

Compilation message (stderr)

knapsack.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization("unroll-loops")
      | 
knapsack.cpp: In function 'int main()':
knapsack.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for (int j = 0; j < w[i].size(); ++j) {
      |                         ~~^~~~~~~~~~~~~
knapsack.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int i = 0; i < w[weight].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~~

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