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
// Karol Kosinski
#include <cstdio>
#include <algorithm>
#include <list>
#define FR(i,a,b) for(int i=(a);i<(b);++i)
//#define DEBUG(x...) printf(x)
#define DEBUG(x...)
using namespace std;

struct event
{
        int ind;
        int is_end;
};

const int NX = 103;
int PK[NX][2], C[NX], D[NX];
event E[2*NX];

inline int etime(const event& a)
{
        return PK[a.ind][a.is_end];
}

bool operator < (const event& a, const event& b)
{
        int val = etime(a) - etime(b);
        if (val != 0)
                return val < 0;
        return a.is_end;
}

int main()
{
        int n, m;
        scanf("%d%d", &n, &m);
        FR(i,0,n)
        {
                int p, k, c;
                scanf("%d%d%d", &p, &k, &c);
                PK[i][0] = p;
                PK[i][1] = k;
                C[i] = c;
                E[2*i] = (event){i, true};
                E[2*i+1] = (event){i, false};
        }
        int n2 = 2 * n;
        sort(E, E + n2);

        int i = 0;
        int time_last = etime(E[i]);
        list<int> L;
        while (etime(E[i]) == time_last)
        {
                L.push_back(E[i].ind);
                DEBUG("i(%c, %d): %d\n", (E[i].is_end ? 'K' : 'P'), E[i].ind, time_last);
                ++i;
        }
        while (i < n2)
        {
                int time_cur = etime(E[i]);
                int dt = time_cur - time_last;
                int capacity = dt * m;
                DEBUG("** time_cur= %d  dt= %d  capacity= %d\n", time_cur, dt, capacity);

                for (int item : L)
                {
                        D[item] = 0;
                        int aux = PK[item][1] - time_cur - C[item];
                        if (aux < 0)
                        {
                                DEBUG("\ta[%d]: K= %d  C= %d  ==> %d\n", item, PK[item][1], C[item], aux);
                                if (-aux > dt or -aux > capacity)
                                {
                                        printf("NIE\n");
                                        return 0;
                                }
                                D[item] = -aux;
                                C[item] += aux;
                                capacity += aux;
                                DEBUG("\t\t: D= %d  C= %d  cap= %d\n", D[item], C[item], capacity);
                        }
                }
                while (i < n2 and E[i].is_end and etime(E[i]) == time_cur)
                {
                        L.remove(E[i].ind);
                        DEBUG("-(%c, %d): %d\n", (E[i].is_end ? 'K' : 'P'), E[i].ind, time_cur);
                        ++i;
                }
                /*
                for (int item : L)
                {
                        int aux = PK[item][1] - time_cur - C[item];
                        if (capacity > 0 and aux == 0 and dt > D[item])
                        {
                                DEBUG("\tb[%d]: K= %d  C= %d  ==> %d\n", item, PK[item][1], C[item], aux);
                                int val = min(C[item], min(capacity, dt - D[item]));
                                D[item] += val;
                                C[item] -= val;
                                capacity -= val;
                                DEBUG("\t\t: D= %d  C= %d  cap= %d\n", D[item], C[item], capacity);
                        }
                }
                */
                L.sort([](int a, int b){ return C[a] - C[b] > 0; });
                for (int item : L)
                {
                        DEBUG("\t[%d]\n", item);
                        if (capacity > 0 and C[item] > 0 and dt > D[item])
                        {
                                DEBUG("\tc[%d]: C= %d\n", item, C[item]);
                                int val = min(C[item], min(capacity, dt - D[item]));
                                D[item] += val;
                                C[item] -= val;
                                capacity -= val;
                                DEBUG("\t\t: D= %d  C= %d  cap= %d\n", D[item], C[item], capacity);
                        }
                }
                while (i < n2 and (not E[i].is_end) and etime(E[i]) == time_cur)
                {
                        L.push_back(E[i].ind);
                        DEBUG("+(%c, %d): %d\n", (E[i].is_end ? 'K' : 'P'), E[i].ind, time_cur);
                        ++i;
                }
                time_last = time_cur;
        }
        printf("TAK\n");
        return 0;
}