제출 #745036

#제출 시각아이디문제언어결과실행 시간메모리
745036glupanKnapsack (NOI18_knapsack)C++14
73 / 100
197 ms262144 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); } ll dp[n+5][s+5]; memset(dp,0,sizeof dp); fore(i,1,n+1) { fore(j,1,s+1) { dp[i][j]+=dp[i-1][j]; ll P=0; int W=0; fore(k,1,kk[i]+1) { W+=we[i]; P+=p[i]; if(j >= W && dp[i-1][j-W] + P > dp[i][j]) dp[i][j] = dp[i-1][j-W] + P; } } } cout << dp[n][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...