Submission #501002

#	Time	Username	Problem	Language	Result	Execution time	Memory
501002		joshualiu555	Knapsack (NOI18_knapsack)	C++17	100 / 100	72 ms	3904 KiB

knapsack

/*
  _____                                     _        _
 / ____|                                   | |      | |
| |  __ _ __ __ _ ___ ___ _   _ _ __   ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
 \_____|_|  \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
                           __/ | |
                          |___/|_|
*/

#pragma gcc target ("avx2")
#pragma gcc optimization ("O3")
#pragma gcc optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using segset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define F0R(i, x, n) for (int i = x; i >= n; i--)
#define TRAV(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define sz size
#define pof pop_front
#define pob pop_back
#define pf push_front
#define pb push_back
#define ins insert
#define mp make_pair
#define rz resize
#define rev reverse
#define lb lower_bound
#define ub upper_bound
// fill for 1
// 0x3f3f3f3f for 1e9
#define mem(a, x) memset(a, x, sizeof(a))

using ll = long long;
const int INF = 2e5 + 5;
const int MOD = 1e9 + 7;
// DLRU
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, -1, 1, 0};

/*
 *
*/

//

void solve() {

}

int s, n;

map<int, vector<pair<int, int>>> groups;
ll dp[2001];

int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(0);

//    ifstream cin(".in");
//    ofstream cout(".out");

//    int t;
//    cin >> t;
//    while (t--) {
//        solve();
//    }

    cin >> s >> n;
    FOR(i, 0, n - 1) {
        int v, w, k;
        cin >> v >> w >> k;
        groups[w].pb(mp(v, k));
    }

    TRAV(it, groups) sort(rall(it -> second));

    mem(dp, -1);
    dp[0] = 0;
    TRAV(it, groups) {
        int weight = it -> first;
        vector<pair<int, int>> items = it -> second;
        F0R(i, s, 0) {
            if (dp[i] >= 0) {
                int cur = i;
                int item = 0;
                int left = items[item].second;
                while (cur + weight <= s) {
                    dp[cur + weight] = max(dp[cur + weight], dp[cur] + items[item].first);
                    cur += weight;
                    left--;
                    if (left == 0) {
                        item++;
                        if (item == items.sz()) break;
                        left = items[item].second;
                    }
                }
            }
        }
    }

    cout << *max_element(dp, dp + s + 1) << '\n';

    return 0;
}

/*
 * 1e5 items are bounded by weight 1 <= w <= 2000
 * Store these weights in map of vectors
 * Sort items of each weight by value
 * DP[i] = highest value at each weight
 * O(S^2 * amortized)
 * Loop through each weight group of items
 * Inner loop through each possible weight
 *
*/

//15 5
//4 12 1
//2 1 1
//10 4 1
//1 1 1
//2 2 1

//20 3
//5000 15 1
//100 1 3
//50 1 4

Compilation message (stderr)

knapsack.cpp:12: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
   12 | #pragma gcc target ("avx2")
      | 
knapsack.cpp:13: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   13 | #pragma gcc optimization ("O3")
      | 
knapsack.cpp:14: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   14 | #pragma gcc optimization ("unroll-loops")
      | 
knapsack.cpp: In function 'int main()':
knapsack.cpp:106:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                         if (item == items.sz()) break;
      |                             ~~~~~^~~~~~~~~~~~~

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