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
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

struct Task {
	int start;
	int end;
	int to_allocate;
	int empty_slots;
};

struct Comp {
	bool operator()(Task t1, Task t2) // is t1 less than t2?
	{
		if (t1.empty_slots < t2.empty_slots) {
			return true;
		}
		if (t1.empty_slots > t2.empty_slots) {
			return false;
		}

		return false;
	}
} my_comp;

template <class ForwardIterator>
std::size_t min_element_index(ForwardIterator first, ForwardIterator last, Comp comp)
{
	ForwardIterator lowest = first;
	std::size_t index = 0;
	std::size_t i = 0;
	if (first == last) return index;
	while (++first != last) {
		++i;
		if (comp(*first,*lowest)) {
			lowest = first;
			index = i;
		}
	}
	return index;
}

short free_cpus[1000001];

int main()
{
	int n, m;
	scanf("%ld %ld", &n, &m);

	vector<Task> tasks;

	int max_time = 0;

	for (int i = 0; i < n; i++)
	{
		int v1, v2, v3;
		scanf("%ld %ld %ld", &v1, &v2, &v3);
		
		Task t;
		t.start = v1;
		t.end = v2 - 1;
		t.to_allocate = v3;
		t.empty_slots = v2 - v1 - v3;

		tasks.push_back(t);

		if (t.end > max_time) {
			max_time = t.end;
		}
	}

	for (int i = 0; i <= max_time; i++)
	{
		free_cpus[i] = m;
	}

	while (tasks.size() > 0) {
		int min_task_index = min_element_index(tasks.begin(), tasks.end(), my_comp);
		Task min_task = tasks[min_task_index];

		int allocated = 0;

		for (int i = min_task.start; i <= min_task.end; i++)
		{
			if (allocated < min_task.to_allocate && free_cpus[i] > 0) {
				// allocate CPU
				free_cpus[i]--;
				allocated++;

				if (free_cpus[i] == 0) {
					// remove time slot
					for (int j = 0; j < tasks.size(); j++) {
						if (j != min_task_index && tasks[j].start <= i && tasks[j].end >= i) {
							tasks[j].empty_slots--;

							if (tasks[j].empty_slots < 0) {
								// FAILED
								printf("NIE\n");
								return 0;
							}
						}
					}
				}
			}
			
			if (allocated == min_task.to_allocate)
			{
				break;
			}
		}

		if (allocated < min_task.to_allocate) {
			// FAILED
			printf("NIE\n");
			return 0;
		}

		tasks.erase(tasks.begin() + min_task_index);
	}

	// SUCCEEDED
	printf("TAK\n");

	return 0;
}