Submission #838998

#	Time	Username	Problem	Language	Result	Execution time	Memory
838998		JosephA	Knapsack (NOI18_knapsack)	C++17	73 / 100	146 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
namespace andrew_tate{
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("O3")
#pragma GCC optimize("omit-frame-pointer")
#pragma GCC optimize("inline")
#define SZ(x) ((int)(x).size()) // size of a container
#define F(i, n) for (int i = 0; i < (int)(n); i++) 
#define ALL(a, x) memset(a, x, sizeof(a)) // set elements of array to some value
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define REMAX(a, b) (a) = max((a), (b)) // set a to the maximum of a and b
#define REMIN(a, b) (a) = min((a), (b));
#define FOREACH(i, t) for (typeof(t.begin()) i = t.begin(); i != t.end(); i++) // traverse an STL data structure
#define all(c) (c).begin(), (c).end() // handy for function like "sort()"
#define contain(c, x) ((c).find(x) != (c).end())
#define present(c, x) (count(all(c), x)>0)
typedef long long ll; // data types used often, but you don't want to type them time by time
typedef unsigned long long ull;
const long double PI = 3.1415926535897932384626;
const int mod = 1000000007;
#define dbg(var) cerr << #var << " = " << (var) << endl; // for debug
#define pb push_back // for vectors
#define SORT(v) sort(all(v))
#define REVERSE(v) reverse(all(v))
#define onecount __builtin_popcount // count number of 1's in a number
#define highbit(x) (63 - __builtin_clzll(x)) // get the index of the highest bit set
#define lowbit(x) __builtin_ctzll(x) // get the index of the lowest bit set
#define bitcount(x) (__builtin_popcount(x) + __builtin_popcount(x >> 32)) // count number of 1's in a number in O(1) time
#define mid(l, r) ((l) + (((r) - (l)) >> 1))
typedef int elem_t;
template <typename T, typename TT>
ostream &operator<<(ostream &s, pair<T, TT> t) { return s << "(" << t.first << "," << t.second << ")"; }
template <typename T>
ostream &operator<<(ostream &s, vector<T> t){ F(i, SZ(t)) s << t[i] << " ";return s;}
template <typename T>
istream &operator>>(istream &in, vector<T>&e){for(auto&x : e) cin >> x; return in;}
template <typename T, typename TT>
istream &operator>>(istream &in, vector<pair<T, TT>>&e){for(auto&x : e) cin >> x.first >> x.second; return in;} 
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll largest_multiple_smaller_than_x(ll a, ll k){ return (k / a) * a;}
ll smallest_multiple_greater_than_x(ll a, ll k){ return ((k + a - 1) / a) * a;}
vector<ll>sieve(ll num){vector<ll>prime;vector<bool>isPrime(num + 1, true);isPrime[0] = isPrime[1] = false;for(int i = 2; i <= num; i++){if(isPrime[i]){prime.push_back(i);for(int j = i * 2; j <= num; j += i) isPrime[j] = false;}}return prime;}
vector<ll>primeFactors(ll num){vector<ll>prime;for(ll i = 2; i * i <= num; i++){while(num % i == 0){prime.push_back(i);num /= i;}}{if(num > 1) prime.push_back(num);}return prime;}
bool is_prime(ll num){if(num < 2) return false;for(ll i = 2; i * i <= num; i++){if(num % i == 0) return false;}return true;}
vector<int>binary(ll num){vector<int>binary;while(num){binary.push_back(num % 2); num >>= 1;} reverse(all(binary)); return binary;}
int decimal(vector<ll>binary){ int num = 0; for(int i = 0; i < binary.size(); i++){num += binary[i] * (1 << i);}return num;}
ll factorial(ll num, ll mod = 1e9+7){ ll fact = 1; for(ll i = 1; i <= num; i++) fact = (fact * i) % mod; return fact;}
ll power(ll x, ll y, ll mod = 1e9+7){ll res = 1; x %= mod; while(y > 0){if(y & 1) res = (res * x) % mod; y >>= 1; x = (x * x) % mod;} return res;}
vector<ll> divisors(ll n){ vector<ll> div; for(ll i = 1; i * i <= n; i++){ if(n % i == 0){ div.push_back(i); if(i * i != n) div.push_back(n / i); } } return div; }
ll mod_inverse(ll num, ll mod = 1e9+7){ return power(num, mod - 2, mod);}
ll NchooseK(ll n, ll k, ll mod = 1e9+1){ll res = 1; k = min(k, n - k); for(ll i = 0; i < k; i++){ res = (res * (n - i)) % mod; res = (res * mod_inverse(i + 1, mod)) % mod;} return res;}
}
using namespace andrew_tate;

struct item{
    ll value, weight, quantity;
};

void solve(){
    int s, n; cin >> s >> n;
    vector<item> items(n); for(auto &x : items) cin >> x.value >> x.weight >> x.quantity;
    for(auto &x : items) {
        REMIN(x.quantity, s / x.weight);
    }
    map<ll, vector<pair<ll, ll>>> mp;
    for(auto &x : items) mp[x.weight].push_back({x.value, x.quantity});
    for(auto &x : mp) SORT(x.second), REVERSE(x.second);
    vector<vector<ll>> dp(n + 1, vector<ll>(s + 1, LONG_LONG_MIN));
    dp[0][0] = 0;
    int i = 0;
    for(auto &x : mp){
        i++;
        for(int weights = 0; weights <= s; weights++) {
            dp[i][weights] = dp[i - 1][weights];
            int copies = 0, idx = 0, profit = 0, curr = 0;
            while((copies + 1) * x.first <= weights && idx < SZ(x.second)){
                copies++;
                curr++;
                profit += x.second[idx].first;
                if(dp[i - 1][weights - copies * x.first] != LONG_LONG_MIN){
                    REMAX(dp[i][weights], dp[i - 1][weights - copies * x.first] + profit);
                }
                if(curr == x.second[idx].second) {
                    curr = 0;
                    idx++;
                } 
            }
        }
    }
    ll ans = 0;
    for(auto &x : dp) for(auto &y : x) REMAX(ans, y);
    cout << ans << "\n";
}
// maybe two pointers, binary search, greedy, dp, dsu, dfs?
// maybe segment tree, graph, math, adhoc, bitmask?

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int TT = 1;
    while(TT--) solve();
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int andrew_tate::decimal(std::vector<long long int>)':
knapsack.cpp:52:62: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 | int decimal(vector<ll>binary){ int num = 0; for(int i = 0; i < binary.size(); i++){num += binary[i] * (1 << i);}return num;}
      |                                                            ~~^~~~~~~~~~~~~~~

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