제출 #744994

#제출 시각아이디문제언어결과실행 시간메모리
744994glupanKnapsack (NOI18_knapsack)C++14
49 / 100
104 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<int>p; vector<int>we; p.push_back(0); we.push_back(0); fore(i,0,n) { int v,w,k; cin >> v >> w >> k; fore(j,0,min(k,s div w)) { p.push_back(v); we.push_back(w); } } int dp[p.size()+5][s+5]; memset(dp,0,sizeof dp); fore(i,1,p.size()) { fore(j,1,s+1) { dp[i][j]+=dp[i-1][j]; if(j >= we[i] && dp[i-1][j-we[i]] + p[i] > dp[i][j]) dp[i][j] = dp[i-1][j-we[i]] + p[i]; } } cout << dp[p.size()-1][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...