제출 #810909

#제출 시각아이디문제언어결과실행 시간메모리
810909AcanikolicKnapsack (NOI18_knapsack)C++14
49 / 100
1087 ms360 KiB
#include <bits/stdc++.h> #define int long long #define pb push_back #define F first #define S second using namespace std; const int N = 2e5+10; const int mod = 1e9+7; const int inf = 1e18; int v[N],w[N],k[N]; signed main(){ ios::sync_with_stdio(false); cin.tie(0); int s,n; cin >> s >> n; for(int i=1;i<=n;i++) { cin >> v[i] >> w[i] >> k[i]; } vector<int>dp(s+1); for(int i=1;i<=n;i++) { vector<int>new_dp = dp; for(int j=1;j<=k[i];j++) { for(int o=w[i]*j;o<=s;o++) new_dp[o] = max(new_dp[o],dp[o-w[i]*j]+v[i]*j); // for(int o=1;o<=s;o++) cout << dp[o] << ' '; // cout << endl; } swap(dp,new_dp); } cout << dp[s]; }
#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...