Submission #1239856

#TimeUsernameProblemLanguageResultExecution timeMemory
1239856MinbaevKnapsack (NOI18_knapsack)C++20
100 / 100
73 ms2888 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define int long long #define ar array #define mrand(a, b) uniform_int_distribution<int>(a, b)(rng) template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} template<class T> using ste = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); namespace FAST { template<typename T, typename F> istream &operator>>(istream &cin, pair<T, F> &p) { cin >> p.first >> p.second; return cin; } template<typename T, typename F> ostream &operator<<(ostream &cout, pair<T, F> &p) { cout << p.first << ' ' << p.second; return cout; } template<typename T> istream &operator>>(istream &cin, vector<T> &a) { for (T &i: a) cin >> i; return cin; } template<typename T> ostream &operator<<(ostream &cout, vector<T> &a) { for (T i: a) cout << i << ' '; return cout; } template<typename T> istream &operator>>(istream &cin, deque<T> &a) { for (T &i: a) cin >> i; return cin; } template<typename T> ostream &operator<<(ostream &cout, deque<T> &a) { for (T i: a) cout << i << ' '; return cout; } } using namespace FAST; const int inf = 1e17 + 7; const int mod = 1e9 + 7; const int N = 1e6 + 5; const int md = 998244353; int binpow(int a, int b, int m){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2,m); return (c*c)%m; } return (binpow(a,b-1,m)*a)%m; } int divi(int a, int b, int m){ return (a*(binpow(b,m-2, m)))%m; } struct Bit { vector<int> b, b2; int n; Bit(int n) { this->n = n + 1; b.assign(n + 1, 0); b2.assign(n+1, 0); } void add(vector<int>&b, int idx, int x){ while(idx <= n){ b[idx] += x; idx += idx & -idx; } } void update(int l, int r, int x){ add(b, l, x); add(b, r+1, -x); add(b2, l, x*(l-1)); add(b2, r+1, -x*r); } int sum(vector<int>&b, int idx){ int res = 0; while(idx > 0){ res += b[idx]; idx -= idx & -idx; } return res; } int pref(int idx){ return sum(b, idx) * idx - sum(b2, idx); } int get(int l, int r){ return pref(r) - pref(l-1); } }; int n,m,k; vector<ar<int,2>>g[2005]; void solve(){ cin >> m >> n; for(int i = 0;i<n;i++){ int a,b,c; cin >> a >> b >> c; g[b].pb({a, c}); } vector<int>dp(2005); for(int i = 1;i<=m;i++){ sort(all(g[i])); reverse(all(g[i])); int u = m / i; int cont = 0; for(auto [cost, cnt]:g[i]){ while(cont < u && cnt > 0){ cnt -= 1; cont += 1; for(int j = m;j>=0;j--){ if(j + i > m)continue; if(dp[j] > 0 || j == 0) umax(dp[j + i], dp[j] + cost); } } } } cout << *max_element(all(dp)) << "\n"; } /* */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;// cin >> tt; while(tt--)solve(); }
#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...