제출 #745014

#제출 시각아이디문제언어결과실행 시간메모리
745014glupanKnapsack (NOI18_knapsack)C++14
0 / 100
1 ms468 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() { ll s,n; cin >> s >> n; vector<ll>p; vector<ll>we; vector<ll>kk; p.push_back(0); we.push_back(0); kk.push_back(0); fore(i,0,n) { ll v,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+1][s+1]; memset(dp,0,sizeof dp); fore(i,1,n+1) { fore(j,1,s+1) { dp[i][j]+=dp[i-1][j]; fore(k,1,kk[i]+1) { we[i]+=we[i]; p[i]+=p[i]; 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[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...