제출 #646922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646922		yellowtomato98	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	212 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{
	ll v,w,n;

	Item(ll a, ll b, ll 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++){
		ll v,w,n; cin >> v >> w >> n;
		Item new_item = Item(v,w,n);
		items.push_back(new_item);
	}
	sort(items.begin(), items.end());

	ll w = 0; int in = 0; ll v = 0;
	while (in < items.size()){
		ll 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;
	// }
}

컴파일 시 표준 에러 (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:84:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Item>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  while (in < items.size()){
      |         ~~~^~~~~~~~~~~~~~

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