Submission #1237515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237515		Duelist1234	Knapsack (NOI18_knapsack)	C++20	49 / 100	148 ms	327680 KiB

knapsack

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <utility>
#include <map>
#define ll long long int
const ll mod=1000000009;
using namespace std;
/*
? Did I test edge cases? (Empty, min/max, 1-element, same elements, etc.)
? Did I reread the full prompt to recheck constraints?
? Does my code handle ties, negatives, zeroes, or duplicates?
? Am I brute-forcing something unnecessarily?
? Am I assuming things not in the problem?
*/
int main(int argc, char** argv) {
	ios_base::sync_with_stdio(false);
		int s,n;
		cin>>s>>n;
		if(n==1)
		{
			int x,y,z;
			cin>>x>>y>>z;
			cout<<min(z,s/y)*x;
			return 0;
		}
		vector<ll> a,weight;
		for(int i=0;i<n;i++)
		{
			int x,y,z;
			cin>>x>>y>>z;
			for(int j=0;j<min(s/y,min(z,s));j++)
			{
				a.push_back(x);
				weight.push_back(y);
			}
		}
		ll dp[s+1][a.size()];
		dp[0][0]=0;
		for(int i=0;i<=s;i++)
		{
			for(int j=0;j<a.size();j++)
			{
				if(i)
				dp[i][j]=dp[i-1][j];
				else
				dp[i][j]=0;
				if(j)
				dp[i][j]=max(dp[i][j-1],dp[i][j]);
				if(i>=weight[j])
				{
					if(j)
					dp[i][j]=max(dp[i][j],dp[i-weight[j]][j-1]+a[j]);
					else
					dp[i][j]=max(dp[i][j],a[j]);
				}
			}
		}
		cout<<dp[s][a.size()-1];
}

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