Submission #648307

#	Time	Username	Problem	Language	Result	Execution time	Memory
648307		yellowtomato98	Knapsack (NOI18_knapsack)	C++17	100 / 100	606 ms	36252 KiB

knapsack

/**
 *   ^~^  ,
 *  ('Y') )
 *  /   \/ 
 * (\|||/)
**/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <numeric>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <tuple>
#include <queue>
using namespace std; 

#define ll long long

void debug(vector<int> x){
	cout << "\n";
	for (int i = 0; i < x.size(); i++){
		cout << x[i] << " ";
	}
	cout << "\n";
}

void debug(vector<vector<ll>> x){
	cout << "\n";
	for (int i = 0; i < x.size(); i++){
		for (int j = 0; j < x[i].size(); j++){
			cout << x[i][j] << " ";
		}
		cout << "\n";
	}
}

void debug(set<int> x){
	cout << "\n";
	for (auto s : x){
		cout << s << " ";
	}
	cout << "\n";
}

void debug(){
	cout << "FLAG" << endl;
}

const int INF = INT32_MAX;
const int MOD = 1e9+7;

// ios_base::sync_with_stdio(0); 
// cin.tie(0);

struct Item{
	int v,w,k;

	Item(int a, int b, int c): v(a), w(b), k(c) {}

	bool operator<(const Item& i) const{
		if (w != i.w){
			return w < i.w;
		}
		return v > i.v;
	}
};

// bool rev(pair<int, int> x, pair<int, int> y){
// 	return x.first > y.first; // sort greatest value to least value
// }

int main(){
	int s,n; cin >> s >> n;
	vector<Item> a;

	for (int i = 0; i < n; i++){
		int v,w,k; cin >> v >> w >> k;
		a.push_back(Item(v,w,k));
	}
	sort(a.begin(), a.end());

	map<int, vector<pair<int, int>>> p;
	for (int i = 0; i < a.size(); i++){
		p[a[i].w].push_back({a[i].v, a[i].k});
	}

	// for (int i = 0; i < a.size(); i++){
	// 	cout << a[i].v << " " << a[i].w << " " << a[i].k << endl;
	// }

	// cout << endl;
	// for (auto it = p.begin(); it != p.end(); it++){
	// 	cout << "new element: " << it->first << endl;
	// 	for (int i = 0; i < it->second.size(); i++){
	// 		cout << (it->second)[i].first << " " << (it->second)[i].second << endl;
	// 	}
	// 	cout << endl;
	// }

	vector<vector<ll>> dp(s+1, vector<ll>(s+1));
	for (int i = 1; i <= s; i++){
		for (int j = 0; j <= s; j++){
			dp[i][j] = dp[i-1][j];
			ll t = 0; int cnt = 1; int cnt2 = 0; int in = 0;

			while (j - cnt*i >= 0 and in < p[i].size()){
				t += p[i][in].first;
				dp[i][j] = max(dp[i-1][j-cnt*i] + t, dp[i][j]);
				cnt2++;
				if (cnt2 == p[i][in].second){
					cnt2 = 0;
					in++;
				}
				cnt++;
			}
			// cout << dp[i][j] << " ";
		}
		// cout << endl;
	}

	cout << dp[s][s] << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'void debug(std::vector<int>)':
knapsack.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 0; i < x.size(); i++){
      |                  ~~^~~~~~~~~~
knapsack.cpp: In function 'void debug(std::vector<std::vector<long long int> >)':
knapsack.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i = 0; i < x.size(); i++){
      |                  ~~^~~~~~~~~~
knapsack.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for (int j = 0; j < x[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~
knapsack.cpp:113: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]
  113 |    while (j - cnt*i >= 0 and in < p[i].size()){
      |                              ~~~^~~~~~~~~~~~~

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