Submission #1234979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234979		hmms127	Knapsack (NOI18_knapsack)	C++20	49 / 100	7 ms	15684 KiB

knapsack

#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;
       	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];



     }


}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27