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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<cstdio>
#include<queue>
#include<list>

using namespace std;

int n, m;

struct Task
{
    int p, k, c;
    int e;
};

class Comp
{
public:
    bool operator()(const Task &a, const Task &b)
    {
        if(a.p == b.p)
        {
            if(a.c == b.c)
                return a.k > b.k;
            return a.c < b.c;
        }
        return a.p > b.p;
    }
};

template <class T, class S, class C>
S& Container(priority_queue<T, S, C>& q)
{
    struct HackedQueue : private priority_queue<T, S, C>
    {
        static S& Container(priority_queue<T, S, C>& q)
        {
            return q.*&HackedQueue::c;
        }
    };
    return HackedQueue::Container(q);
}

Task tab[100];

priority_queue<Task, vector<Task>, Comp > toDoTasks;
list<Task> doingTasks;

main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        scanf("%d %d %d", &tab[i].p, &tab[i].k, &tab[i].c);
        tab[i].e = tab[i].p + tab[i].c;
    }
    toDoTasks = priority_queue<Task, vector<Task>, Comp>(tab, tab+n, Comp());

    bool success = true;

    while(!toDoTasks.empty() && success)
    {
        Task t = toDoTasks.top();
        toDoTasks.pop();
        if(doingTasks.empty())
        {
            doingTasks.push_back(t);
        }
        else
        {
            list<Task>::iterator it = doingTasks.begin();
            while(it != doingTasks.end())
            {
                if(it->e <= t.p)
                {
                    it = doingTasks.erase(it);
                }
                else
                {
                    it++;
                }
            }
            if(doingTasks.size() < m)
            {
                doingTasks.push_back(t);
            }
            else
            {
                it = doingTasks.begin();
                while(it != doingTasks.end())
                {
                    it->c -= t.p - it->p;
                    it->p = t.p;
                    it++;
                }

                doingTasks.push_back(t);
                it = doingTasks.begin();
                int firstEnd = 1000001;
                while(it != doingTasks.end() && it->k - it->p == it->c)
                {
                    if(it->e < firstEnd)
                        firstEnd = it->e;
                    it++;
                }
                if(it == doingTasks.end())
                    success = false;
                else
                {
                    list<Task>::iterator shortest = it;
                    it++;
                    while(it != doingTasks.end())
                    {
                        if(it->k - it->p > it->c && it->c < shortest->c)
                        {
                            if(shortest->e < firstEnd)
                                firstEnd = shortest->e;
                            shortest = it;
                        }
                        else
                        {
                            if(it->e < firstEnd)
                                firstEnd = it->e;
                        }
                        it++;
                    }

                    vector<Task> &tasks = Container(toDoTasks);
                    for(int ii = 0; ii < tasks.size(); ii++)
                    {
                        if(tasks[ii].e < firstEnd)
                            firstEnd = tasks[ii].e;
                    }

                    if(shortest->k - firstEnd < shortest->c)
                        firstEnd = shortest->k - shortest->c;
                    shortest->p = firstEnd;

                    shortest->e = shortest->p + shortest->c;
                    toDoTasks.push(*shortest);
                    doingTasks.erase(shortest);
                }
            }
        }
    }

    if(success)
        printf("TAK\n");
    else
        printf("NIE\n");
}