Submission #862890

#	Time	Username	Problem	Language	Result	Execution time	Memory
862890		Drevz	Knapsack (NOI18_knapsack)	C++11	100 / 100	69 ms	34376 KiB

knapsack

#include <bits/stdc++.h>
 
using namespace std;
typedef const char* cstr;
typedef unsigned long long ull;
typedef long long ll;
 
#define MottoHayaku ios_base::sync_with_stdio(false); cin.tie(0);
#define FIO(filename) \
ifstream cin(#filename".in"); \
ofstream cout(#filename".out");
#define rep(i, n) for (int i=0;i<n;++i)
#define per(i, n) for (int i=n-1;i>=0;--i)
#define FOR(i, s, n) for (int i=s;i<n;++i)
#define ROF(i, e, n) for (int i=n-1;i>=e;--i)
#define forin(x, o) for (auto& x : o)
#define foreach(x, o) for (auto x : o)
#define loop(x) while (x--)
#define mid(l, r) (l + (r - l) / 2)
#define left(i) ((i*2)+1)
#define right(i) ((i*2)+2)
#define parent(i) ((i-1)/2)
#define mod 1000000007
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define xx first
#define yy second
#define key first
#define value second
#define endl '\n'
#define no "No"
#define ye "Yes"
#define imp "IMPOSSIBLE"
#define i64_min -9223372036854775808

int main() {
//	ifstream cin("input.txt");
	MottoHayaku;
	int limit, n; cin >> limit >> n;
	map<short, vector<pair<int, int> > > by_w;
	rep(i, n){
		short w;
		int v, k; cin >> v >> w >> k;
		by_w[w].push_back({v, k});
	}
	
	vector<vector<long long> > dp(by_w.size() + 1, vector<long long>(limit + 1, i64_min));
	
	dp[0][0] = 0;
	int at = 1;
	
	map<short, vector<pair<int, int> > >::iterator it;
	
	for (it = by_w.begin(); it != by_w.end(); ++it){
		short item_wei = it->first;
		sort(it->second.begin(), it->second.end(), greater<pair<int, int> >());
		
		for (int space = 0; space <= limit; ++space){
			dp[at][space] = dp[at - 1][space];
			int copies = 0; // count of items weighted w
			int curr_t = 0; // current items type
			int curr_t_cnt = 0; // curr items type's count
			long long prof = 0; // profit
			
			while ((copies + 1) * item_wei <= space && curr_t < it->second.size()){
				++copies;
				prof += it->second[curr_t].first;
				if (dp[at - 1][space - copies * item_wei] != i64_min){
					dp[at][space] = max(dp[at][space], dp[at - 1][space - copies * item_wei] + prof);
				}
				
				++curr_t_cnt;
				if (curr_t_cnt == it->second[curr_t].second){
					curr_t_cnt = 0;
					++curr_t;
				}
			}
		}
		++at;
	}
	
	cout << *std::max_element(dp.back().begin(), dp.back().end()) << endl;
	return 0;
}

Compilation message (stderr)

knapsack.cpp:49:78: warning: integer constant is so large that it is unsigned
   49 |  vector<vector<long long> > dp(by_w.size() + 1, vector<long long>(limit + 1, i64_min));
      |                                                                              ^~~~~~~
knapsack.cpp:70:50: warning: integer constant is so large that it is unsigned
   70 |     if (dp[at - 1][space - copies * item_wei] != i64_min){
      |                                                  ^~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:67:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    while ((copies + 1) * item_wei <= space && curr_t < it->second.size()){
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~

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