Submission #1147148

#TimeUsernameProblemLanguageResultExecution timeMemory
1147148liangjeremyKnapsack (NOI18_knapsack)C++20
100 / 100
62 ms8616 KiB
#include<bits/stdc++.h> #include<random> using namespace std; using db=double; using ll=long long; using sll=__int128;//super long long using lb=long double;//lb is slow //numbers for hashing: b(19260817),mod(998244353) //another number for hashing:b(137) only // freopen("snakes.in", "r", stdin); // freopen("snakes.out", "w", stdout); int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll s,n; cin>>s>>n; vector<priority_queue<ll>>v(s+1); for(ll i=0; i<n; i++){ ll vi,wi,ki; cin>>vi>>wi>>ki; vector<ll>tot; ll cur=1; ll sum=0; while(sum+cur<=ki){ tot.push_back(cur); sum+=cur; cur*=2; } if(ki-sum>0)tot.push_back(ki-sum); for(auto x:tot){ if(wi*x<=s){ v[wi*x].push(vi*x); } } } vector<ll>dp(s+1,-1e9); dp[0]=0; for(ll i=1; i<=s; i++){ ll sum=0; while(v[i].size()&&sum+i<=s){ sum+=i; ll val=v[i].top(); v[i].pop(); for(ll j=s; j>=i; j--){ dp[j]=max(dp[j],dp[j-i]+val); } } } cout<<*max_element(dp.begin(),dp.end()); }
#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...