Submission #1262242

#TimeUsernameProblemLanguageResultExecution timeMemory
1262242settopKnapsack (NOI18_knapsack)C++20
100 / 100
73 ms37956 KiB
#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; #define int long long #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update> #define eb emplace_back #define S second #define dbg(v) cerr << #v << " = " << v << "\n" #define F first #define fall(i,a,n) for(int i=a;i<=n;i++) #define rfall(i,a,n) for(int i=a;i>=n;i--) #define pb push_back #define all(x) x.begin(),x.end() #define lsb(x) (x & -x) #define sz(x) (int)x.size() const int MAXN=2e3+10; const int MAXL=1e5+10; const int inf=1e18; const int MOD=1e9+7; typedef pair<int,int> pii; typedef tuple<int,int,int>trio; typedef tuple<int,int,int,int> squad; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n,k,dp[MAXN],tira[MAXN],aux[MAXN]; multiset<pii> st[MAXN]; vector<int> v[MAXN]; int32_t main(){ std::ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen("odometer.in","r",stdin); //freopen("odometer.out","w",stdout); cin>>k>>n; fall(i,1,k) dp[i]=-inf; int ans=0; fall(i,1,n){ int val,p,q; cin>>val>>p>>q; st[p].insert({-val,q}); } fall(i,1,k){ while(st[i].size()>0){ auto it=st[i].begin(); st[i].erase(it); auto [x,u]=*it; for(int j=1;j<=u && sz(v[i])<=k;j++) v[i].pb(-x); if(v[i].size()==k) break; } } fall(i,1,k){ rfall(j,k,1){ int r=1,ans=0; while(r<=sz(v[i]) && j-r*i>=0){ ans+=v[i][r-1]; dp[j]=max(dp[j],dp[j-r*i]+ans); r++; } } } int x=0; fall(i,0,k) x=max(x,dp[i]); cout<<x<<"\n"; }
#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...