| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1234998 | hmms127 | Knapsack (NOI18_knapsack) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <climits>
#include <cfloat>
#include <cctype>
#include <cstdarg>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <bitset>
#include <vector>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <iterator>
#include <string>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <limits>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <array>
#include <forward_list>
#include <random>
#include <regex>
#include <complex>
using namespace std;
#define f1(n) for(int i=0;i<n;i++)
#define e '\n'
#define f2(m,n,q) for(int i=m;i<n;i+=q)
#define f3(n) for(int j=0;j<n;j++)
#define f4(m,n,q) for(int j=m;j<n;j+=q)
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define pb push_back
typedef long long ll;
const int N=2e3+1;
const int mod=998244353;
const int inf=1e18,sqr=448;
vector<int>adj[N];
int dp[1005][N];
int32_t main()
{
speed;
int tt=1;//cin>>tt;
while(tt--){
//freopen("teamwork.in","r",stdin);
//freopen("teamwork.out","w",stdout);
int n,w;cin>>w>>n;
if(n==1){
int x,y,k;cin>>x>>y>>k;
cout<<min(k,w/y)*x;
return 0;
}
vector<array<int,2>> a;
f1(n){
int w,v,k;cin>>v>>w>>k;
k=min(k,2000);
while(k--)a.pb({v,w});
}
for(int i=(int)a.size()-1;i>=0;i--){
for(int j=w;j>=0;j--){
dp[i][j]=max(dp[i+1][j],(j+a[i][1]<=w ? dp[i+1][j+a[i][1]]+a[i][0]:0));
}
}
cout<<dp[0][0];
}
}