Submission #1147123

#TimeUsernameProblemLanguageResultExecution timeMemory
1147123fonikos01Knapsack (NOI18_knapsack)C++20
12 / 100
1 ms328 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<ll> V(N); vector<ll> W(N); vector<ll> K(N); for (int i = 0; i < N; i++) { cin >> V[i] >> W[i] >> K[i]; } vector<ll> dp(S+1); for (int i = 0; i < N; i++) { vector<vector<pair<ll,ll>>> monoDp(W[i], vector<pair<ll,ll>>(0)); vector<ll> monoPointer(W[i], 0); vector<ll> newdp(S+1, 0); for (int j = 0; j <= S; j++) { ll monoIdx = j%W[i]; while (monoDp[monoIdx].size() > 0 && monoDp[monoIdx][monoPointer[monoIdx]].second < j-K[i]*W[i]) { monoPointer[monoIdx]++; } if (monoPointer[monoIdx] < monoDp[monoIdx].size()) { newdp[j] = max(newdp[j], monoDp[monoIdx][monoPointer[monoIdx]].first+V[i]*((j-monoDp[monoIdx][monoPointer[monoIdx]].second)/W[i])); } while (monoDp[monoIdx].size() > 0 && monoDp[monoIdx].back().first+V[i]*((j-monoDp[monoIdx].back().second)/W[i]) <= dp[j]) { monoDp[monoIdx].pop_back(); if (monoPointer[monoIdx] >= monoDp[monoIdx].size() && monoDp[monoIdx].size() > 0) { monoPointer[monoIdx] = monoDp[monoIdx].size()-1; } } monoDp[monoIdx].push_back({dp[j], j}); } dp = newdp; } ll ans = 0; for (int i = 0; i <= S; i++) { ans = max(ans, dp[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...