Submission #680504

#	Time	Username	Problem	Language	Result	Execution time	Memory
680504		ajstillpracticin	Knapsack (NOI18_knapsack)	C++17	100 / 100	102 ms	34420 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define fi first
#define se second

int xdir[4]{1,0,-1,0};
int ydir[4]{0,1,0,-1};

void setIO(string filename=""){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(filename.size()){
		freopen((filename + ".in").c_str(), "r", stdin);
		freopen((filename + ".out").c_str(), "w", stdout);
	}
}

const int INF=(int) 1e9;
const int M= 1e9+7;

//
const int MAXN = 1000;

int main() {

	setIO();

	int s,n;
	cin >> s >> n;

	map<int, vector<pair<int,int>>> weight;
	for(int i=0;i<n;++i){
		int x,y,z;
		cin >> x >> y >> z;

		if(y<=s && z>0)
			weight[y].push_back({x,z});
	}

	vector<vector<ll>> dp(weight.size()+1,vector<ll>(s+1,INT_MIN));
	dp[0][0]=0;

	int cur=1;
	for(auto& i : weight){
		ll w=i.fi;
		vector<pair<int,int>> items=i.se;
		sort(items.begin(),items.end(),greater<pair<int,int>>());
		for(int i=0;i<=s;++i){
			dp[cur][i]=dp[cur-1][i];

			int copies=0;
			int type=0;
			int used=0;
			ll profit=0;

			while((copies+1)*w<=i && type<items.size()){
				++copies;
				profit+=items[type].fi;
				if(dp[cur-1][i-copies*w]!=INT_MIN){
					dp[cur][i]=max(dp[cur][i],dp[cur-1][i-copies*w]+profit);
				}

				++used;
				if(used==items[type].se){
					used=0;
					++type;
				}
			}
		}

		++cur;
	}

	cout << *max_element(dp.back().begin(), dp.back().end()) << "\n";
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:57:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    while((copies+1)*w<=i && type<items.size()){
      |                             ~~~~^~~~~~~~~~~~~
knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   freopen((filename + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   freopen((filename + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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