Submission #646921

#	Time	Username	Problem	Language	Result	Execution time	Memory
646921		yellowtomato98	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	300 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;
	int w; 
	int n;

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

	bool operator<(const Item& i) const{
		return (double)v/w > (double)i.v/i.w; // sort greatest to least
	}
};

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

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

	int w = 0; int in = 0; int v = 0;
	while (in < items.size()){
		int m_items = (s-w)/items[in].w;
		if (m_items >= items[in].n){
			v += items[in].n*items[in].v;
			w += items[in].n*items[in].w;
			in++;
			continue;
		}
		v += m_items*items[in].v; 
		break;
	}
	cout << v;

	// debug();
	// for (int i = 0; i < n; i++){
	// 	cout << items[i].v << " " << items[i].w << " " << items[i].n << 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:86:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  while (in < items.size()){
      |         ~~~^~~~~~~~~~~~~~

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