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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;

/*******************************************************************************/
// Poniższy kod algorytmu szukania maksymalnego przepływu (metoda push-relabel)
// zapożyczony został z udostępnionej biblioteczki kodów Bartosza Walczaka.

#define FOR(i,a,b) for (int i=(a); i<(int)(b); ++i)
#define FORD(i,a,b) for (int i=(a)-1; i>=(int)(b); --i)
#define FORE(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)

const int FLOW_MAX = 305;
int FLOW_N, FLOW_S, FLOW_T;
int FLOW_EDGE[FLOW_MAX][FLOW_MAX];
int FLOW_LABEL[FLOW_MAX];
int FLOW_EXCESS[FLOW_MAX];
int FLOW_CUR[FLOW_MAX];
bool FLOW_INQ[FLOW_MAX];

void relabel() {
   queue<int> Q;
   fill_n(FLOW_LABEL, FLOW_N, INT_MAX-1);
   FLOW_LABEL[FLOW_T]=0;
   Q.push(FLOW_T);
   while (!Q.empty()) {
      int j=Q.front(); Q.pop();
      FOR(i,0,FLOW_N) if (FLOW_LABEL[i]==INT_MAX-1 && FLOW_EDGE[i][j]) {
         FLOW_LABEL[i]=FLOW_LABEL[j]+1;
         Q.push(i);
      }
   }
}

int compute_flow() {
   FOR(i,0,FLOW_N) if (i!=FLOW_S) {
      FLOW_EDGE[i][FLOW_S]+=FLOW_EXCESS[i]=FLOW_EDGE[FLOW_S][i];
      FLOW_EDGE[FLOW_S][i]=0;
   }
   int cnt=FLOW_N; relabel();
   queue<int> Q;
   FOR(i,0,FLOW_N) if (i!=FLOW_S && i!=FLOW_T) {
      if (FLOW_EXCESS[i]) Q.push(i);
      FLOW_INQ[i]=FLOW_EXCESS[i];
      FLOW_CUR[i]=0;
   }
   FLOW_INQ[FLOW_S]=FLOW_INQ[FLOW_T]=true;
   while (!Q.empty()) {
      int i=Q.front(); Q.pop();
      FLOW_INQ[i]=false;
      while (FLOW_EXCESS[i] && FLOW_LABEL[i]<FLOW_N) {
         int j=FLOW_CUR[i];
         if (j==FLOW_N) {
            if (--cnt) {
               FLOW_LABEL[i]=INT_MAX-1;
               FOR(k,0,FLOW_N) if (FLOW_EDGE[i][k]) FLOW_LABEL[i]=min(FLOW_LABEL[i], FLOW_LABEL[k]+1);
            }
            else { cnt=FLOW_N; relabel(); }
            FLOW_CUR[i]=0;
         }
         else if (FLOW_EDGE[i][j] && FLOW_LABEL[i]==FLOW_LABEL[j]+1) {
            int f=min(FLOW_EXCESS[i], FLOW_EDGE[i][j]);
            FLOW_EDGE[i][j]-=f; FLOW_EDGE[j][i]+=f;
            FLOW_EXCESS[i]-=f; FLOW_EXCESS[j]+=f;
            if (!FLOW_INQ[j]) { Q.push(j); FLOW_INQ[j]=true; }
         }
         else ++FLOW_CUR[i];
      }
   }
   return FLOW_EXCESS[FLOW_T];
}

/*******************************************************************************/

int n, m, task_sum;
vector<int> P, K, C;

set<int> PS;

int main()
{
    // Read data
    scanf("%d %d", &n, &m); task_sum = 0;
    P.resize(n); K.resize(n); C.resize(n);
    FOR(i, 0, n)
    {
        scanf("%d %d %d", &P[i], &K[i], &C[i]);
        PS.insert(P[i]);
        PS.insert(K[i]);
        task_sum += C[i];
    }

    // Init basic data in FLOW graph
    FLOW_N = n + (PS.size() - 1) + 2;
    FLOW_S = FLOW_N - 2;
    FLOW_T = FLOW_N - 1;
    FOR(i, 0, FLOW_N) memset(FLOW_EDGE[i], 0, FLOW_N);
    memset(FLOW_LABEL, 0, FLOW_N);
    memset(FLOW_EXCESS, 0, FLOW_N);
    memset(FLOW_CUR, 0, FLOW_N);
    memset(FLOW_INQ, false, FLOW_N);
    FOR(i, 0, n) FLOW_EDGE[FLOW_S][i] = C[i];

    // Create period nodes
    int prev_point = -1, node_id = n - 1;
    FORE(it, PS){
        int period_capacity = *it - prev_point;
        if (prev_point != -1)
        {
            FLOW_EDGE[node_id][FLOW_T] = period_capacity * m;
            FOR(i, 0, n) if (prev_point >= P[i] && *it <= K[i]) FLOW_EDGE[i][node_id] = period_capacity;
        }
        prev_point = *it;
        ++node_id;
    }

    // Calculate result
    if (compute_flow() >= task_sum) printf("TAK\n"); else printf("NIE\n");
}