제출 #745045

#제출 시각아이디문제언어결과실행 시간메모리
745045glupanKnapsack (NOI18_knapsack)C++14
73 / 100
1082 ms2388 KiB
#include <bits/stdc++.h> #define div / #define ll long long #define fore(i, l, r) for(int i=int(l); i<int(r); i++) #define sz(a) int((a).size()) using namespace std; const int INF = 1e9; const int MX = 5e5 + 23; const int MOD = 1000000007; const int MAX_N = 5e5+23; const int N = 1e6; void solve() { int s,n; cin >> s >> n; vector<ll>p; vector<int>we, kk; p.push_back(0); we.push_back(0); kk.push_back(0); fore(i,0,n) { ll v; int w,k; cin >> v >> w >> k; k=min(k, s div w); p.push_back(v); we.push_back(w); kk.push_back(k); } vector<ll>prev(s+5, 0), cur(s+5); fore(i,1,n+1) { fore(j,1,s+1) { cur[j]=prev[j]; ll P=0; int W=0; fore(k,1,kk[i]+1) { W+=we[i]; P+=p[i]; if(j >= W && prev[j-W] + P > cur[j]) cur[j] = prev[j-W] + P; } } prev=cur; } cout << prev[s] << endl; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); //freopen("feast.in","r",stdin); //freopen("feast.out","w",stdout); int t=1; while(t--) 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...