1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <queue>
#include <vector>

struct Enemy
{
	Enemy(unsigned int _id): id(_id) {};
	unsigned int id;
	int cost;
	int capture;
	int profit;
};

struct CompareProfitable
{
	bool operator()(const Enemy& first, const Enemy& second) const
	{
		return first.cost > second.cost;
	}
};

struct CompareNonProfitable
{
	bool operator()(const Enemy& first, const Enemy& second) const
	{
		return (first.cost < second.cost) or 
		       ((first.cost == second.cost) and (first.profit < second.profit));
	}
};
unsigned int order[1000000];

int main()
{
	std::priority_queue<Enemy, std::vector<Enemy>, CompareProfitable> profitable;
	std::priority_queue<Enemy, std::vector<Enemy>, CompareNonProfitable> nonProfitable;
	unsigned int enemies;
	std::cin >> enemies;
	int resources;
	std::cin >> resources;
	for (unsigned int i=1; i<=enemies; ++i)
	{
		Enemy enemy(i);
		std::cin >> enemy.cost;
		std::cin >> enemy.capture;
		enemy.profit = enemy.capture-enemy.cost;
		if (enemy.profit<0)
		  nonProfitable.push(enemy);
		else
		  profitable.push(enemy);	 
	}
	bool alive = true;
	unsigned int j=0;
	while (alive and (not profitable.empty()))
	{
		alive = (resources > profitable.top().cost);
		resources += profitable.top().profit;
		order[j++] = profitable.top().id;
		profitable.pop();
	}
	while (alive and (not nonProfitable.empty()))
	{
		alive = (resources > nonProfitable.top().cost);
		resources += nonProfitable.top().profit;
		order[j++] = nonProfitable.top().id;
		nonProfitable.pop();
	}
	std::cout << (alive ? "TAK" : "NIE");
	if (alive)
	{
		std::cout << std::endl;
		unsigned int i;
		for (i=0; i<enemies-1; ++i)
		{
			std::cout << order[i] << " ";
		}
		std::cout << order[i];
	}
	return 0;
}