Submission #1147979

#TimeUsernameProblemLanguageResultExecution timeMemory
1147979fonikos01Knapsack (NOI18_knapsack)C++20
100 / 100
42 ms2972 KiB
#include <bits/stdc++.h> #include <vector> #include <tuple> // #include "debugging.h" // #include <atcoder/lazysegtree> // #include <atcoder/dsu> // #include <atcoder/segtree> // #include <atcoder/modint> // using namespace atcoder; // using mint = static_modint<998244353>; using namespace std; const int LARGE = 1e9; #define all(x) (x).begin(), (x).end() using ll = long long; typedef pair<ll, ll> pi; mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; struct chash { /// use most bits rather than just the lowest ones const uint64_t C = ll(4e18 * acos(0)) + 71; // large odd number const int RANDOM = rng(); ll operator()(ll x) const { return __builtin_bswap64((x ^ RANDOM) * C); } }; /// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html /// template<class K,class V> using um = unordered_map<K,V,chash>; template <class K, class V> using ht = gp_hash_table<K, V, chash, equal_to<K>, direct_mask_range_hashing<>, linear_probe_fn<>, hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<>, true>>; template <class K, class V> V get(ht<K, V>& u, K x) { auto it = u.find(x); return it == end(u) ? 0 : it->s; } // bool cmp(pair<ll, ll> a, pair<ll, ll> b) // { // if (a.second < b.second) // return true; // return false; // } // struct node // { // // part which will store data // int data; // // pointer to the previous node // struct node *prev; // // pointer to the next node // struct node *next; // }; // struct trienode // { // vector<trienode*> desc; // vector<ll> descExist; // trienode(ll M) { // desc.resize(M); // descExist.resize(M); // } // }; const int MOD = 998244353; // template<int MOD, int RT> struct mint { // static const int mod = MOD; // static constexpr mint rt() { return RT; } // primitive root // int v; // explicit operator int() const { return v; } // mint():v(0) {} // mint(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; } // mint& operator+=(mint o) { // if ((v += o.v) >= MOD) v -= MOD; // return *this; } // mint& operator-=(mint o) { // if ((v -= o.v) < 0) v += MOD; // return *this; } // mint& operator*=(mint o) { // v = int((ll)v*o.v%MOD); return *this; } // friend mint pow(mint a, ll p) { assert(p >= 0); // return p==0?1:pow(a*a,p/2)*(p&1?a:1); } // friend mint inv(mint a) { assert(a.v != 0); return pow(a,MOD-2); } // friend mint operator+(mint a, mint b) { return a += b; } // friend mint operator-(mint a, mint b) { return a -= b; } // friend mint operator*(mint a, mint b) { return a *= b; } // }; // using mi = mint<(int)MOD, 5>; // struct mySeg // { // vector<ll> A; // ll N; // void build() // { // A.resize(N * 2); // for (int i = 0; i < N; i++) // A[i + N] = A[i]; // for (int i = N - 1; i > 0; i--) // A[i] = min(A[i << 1], A[i << 1 ^ 1]); // // for (auto el : A) cout << el << " "; // } // void set(ll idx, ll val) // { // idx += N; // A[idx] = val; // for (int i = idx >> 1; i > 0; i >>= 1) // A[i] = min(A[i << 1], A[i << 1 ^ 1]); // // for (auto el : A) cout << el << " "; // } // ll minnQuery(ll l, ll r) // { // ll minn = INT64_MAX; // for (l = l + N, r = r + N; l < r; l >>= 1, r >>= 1) // { // if (l % 2) // minn = min(minn, A[l++]); // if (r % 2) // minn = min(minn, A[--r]); // } // return minn; // } // }; // template <class T> // class myFen // { // private: // int N; // vector<T> A; // vector<T> BIT; // public: // myFen(int size) : N(size), A(size + 1), BIT(size + 1) {} // void set(ll idx, ll val) // { // update(idx, val - A[idx]); // A[idx] = val; // } // void update(ll idx, ll diff) // { // for (idx = idx; idx <= N; idx += idx & (-idx)) // BIT[idx] += diff; // } // ll sumQuery(ll idx) // { // if (idx == 0) // return 0LL; // ll summ = 0; // for (idx = idx; idx > 0; idx -= idx & (-idx)) // summ += BIT[idx]; // return summ; // } // }; // mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); // class HashedString { // private: // // change M and B if you want // static const ll M = (1LL << 61) - 1; // static const ll B; // // pow[i] contains B^i % M // static vector<ll> pow; // // p_hash[i] is the hash of the first i characters of the given string // vector<ll> p_hash; // __int128 mul(ll a, ll b) { return (__int128)a * b; } // ll mod_mul(ll a, ll b) { return mul(a, b) % M; } // public: // HashedString(const string &s) : p_hash(s.size() + 1) { // while (pow.size() < s.size()) { pow.push_back(mod_mul(pow.back(), B)); } // p_hash[0] = 0; // for (int i = 0; i < s.size(); i++) { // p_hash[i + 1] = (mul(p_hash[i], B) + s[i]) % M; // } // } // ll get_hash(int start, int end) { // ll raw_val = p_hash[end + 1] - mod_mul(p_hash[start], pow[end - start + 1]); // return (raw_val + M) % M; // } // }; // vector<ll> HashedString::pow = {1}; // const ll HashedString::B = uniform_int_distribution<ll>(0, M - 1)(rng); ll power(ll x, ll y, ll M) { if (y == 0) return ll(1); ll p = power(x, y / ll(2), M) % M; p = (p * p) % M; return (y % ll(2) == 0) ? p : (x * p) % M; } int solve() { ll S, N; cin >> S >> N; vector<vector<pair<ll,ll>>> W(S+1); for (int i = 0; i < N; i++) { ll v, w, k; cin >> v >> w >> k; if (w <= S) { W[w].push_back(make_pair(v, k)); } } vector<vector<ll>> dp(2, vector<ll>(S+1, 0)); ll dpState = 0; for (int i = 1; i <= S; i++) { sort(all(W[i]), greater<pair<ll,ll>>()); vector<ll> temp(0); for (int j = 0; j < W[i].size(); j++) { for (int k = 0; k < W[i][j].second; k++) { temp.push_back(W[i][j].first); if (temp.size() > 2000) break; } if (temp.size() > 2000) break; } if (temp.size() == 0) continue; vector<ll> ps(temp.size()+1, 0); for (int j = 0; j < temp.size(); j++) { ps[j+1] = ps[j] + temp[j]; } for (int j = 0; j <= S; j++) { ll currW = j; for (int k = 1; k < ps.size(); k++) { currW += i; if (currW > S) break; dp[dpState^1][currW] = max(dp[dpState^1][currW], ps[k] + dp[dpState][j]); } dp[dpState^1][j] = max(dp[dpState^1][j], dp[dpState][j]); } dpState ^= 1; } ll ans = 0; for (int i = 0; i <= S; i++) { ans = max(ans, dp[dpState][i]); } cout << ans << '\n'; return 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // freopen("spainting.in", "r", stdin); // freopen("spainting.out", "w", stdout); // ll caseCnt = 1; // ll T; // cin >> T; // while (T--) // { solve(); // cout << "Case #"<< caseCnt << ": " << ans << '\n'; // caseCnt++; // } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...