Submission #1079510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079510		Captain_Katsura	Knapsack (NOI18_knapsack)	C++17	100 / 100	70 ms	3924 KiB

knapsack

#include <iostream>
#include <cmath>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <tuple>
#include <numeric>
#include <map>
#include <bit>
#include <fstream>
#include <functional>
#include <array>
#include <chrono>
// #include<bits/stdc++.h>
/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
using namespace std;

struct pair_hash {
	inline std::size_t operator()(const std::pair<int, int>& v) const {
		return v.first * 31 + v.second;
	}
}; // for unordered set of pairs

struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
	// http://xorshift.di.unimi.it/splitmix64.c
	x += 0x9e3779b97f4a7c15;
	x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
	x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
	return x ^ (x >> 31);
}

size_t operator()(uint64_t x) const {
	static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
	return splitmix64(x + FIXED_RANDOM);
}
};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
#define rep(i, a, n) for(int i = a; i < n; ++i)
#define exists(s, e) (s.find(e) != s.end())
#define def_sort(s) (sort(s.begin(), s.end()))
#define def_reverse(s) (sort(s.rbegin(), s.rend()))
#define lsone(s) (s & -s)
#define endl '\n'

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
const long long INF = 1LL << 62;
using ll = long long;
using ull = unsigned long long;
typedef vector<int> vi;

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 }; // first 4 for urdl rest for diags
int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

ll MOD = 1e9 + 7;
int rows, cols;

bool ok(int i, int j) {
	return (i >= 0 && j >= 0 && i < rows && j < cols);
}

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
ull read_int() {
	bool minus = false;
	ull result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch - '0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result * 10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}

template <typename T>
T mod(T a, T b = 1) {
	T rez = a % b;
	if (rez < 0)
		rez += b;
	return rez;
}

void add(ll& a, ll b) {
	a += b;
	if (a >= MOD) a -= MOD;
}

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

void solve() {
	int n, s; cin >> s >> n;

	//group on weights 
	map<int,vector<pair<int,int>>>weights;

	for(int i = 0; i < n;++i)
	{
		int v,w,k;cin >> v>>w>>k;
		if(w <= s)
		weights[w].push_back({v,k});
	}
	int dp[2][s+1];
	int prev = 0;
	int curr = 1;
	memset(dp,0,sizeof(dp));
	for(auto &[w,item] : weights)
	{
		//always make sense to take higher value elements for same weight first
		sort(item.rbegin(),item.rend());
		for(int i = 1; i <= s; ++i)
		{
			int val = 0;
			int curr_item = -1;
			int wt_cnt = 0;
			int tmp = 0;
			while (i - wt_cnt*w >= 0)
			{
				if(tmp == 0)
				{
					curr_item++;
					if(curr_item == item.size())break;
					tmp = item[curr_item].second;
					continue;
				}				
				val += item[curr_item].first;
				wt_cnt++;
				tmp--;
				if(i - wt_cnt*w >= 0)
				{
					dp[curr][i] = max({dp[prev][i],dp[prev][i - wt_cnt*w]+val,dp[curr][i]});
				}
			}
			
		}
		curr^=1;
		prev^=1;
	}
	curr^=1;
	int res = 0;
	for(int i = 0; i <= s; ++i){res = max(res,dp[curr][i]);}
	cout << res<< endl;
}

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	// freopen("div7.in", "r", stdin);
	// freopen("div7.out", "w", stdout);
	// cout << setprecision(50);
	int tc = 1;
	// cin >> tc;
	while (tc--)
		solve();
cerr << "Time elapsed:" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |      if(curr_item == item.size())break;
      |         ~~~~~~~~~~^~~~~~~~~~~~~~

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