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

const int MAXV=500;
const int MAX_CAP = 1000000000;
vector<vector<int>> G;
int cap[MAXV][MAXV];

int add_vertex() {
    G.push_back(vector<int>(0));
    return G.size() - 1;
}

void add_edge(int from, int to, int c) {
    G[from].push_back(to);
    if(!cap[to][from]) G[to].push_back(from);
    cap[from][to]=c;
}


int find_path(int sink, int source) {
    queue<int> Q;
    Q.push(source);
    vector<bool> visited = vector<bool>(G.size(), false);
    vector<int> from = vector<int>(G.size(),-1);
        visited[source]=true;
    while(!Q.empty()) {
        int p = Q.front();Q.pop();
        if(p==sink)break;
        for(auto it = G[p].begin();it!=G[p].end();it++){
            int q = *it;
            if(cap[p][q]==0 || visited[q])continue;
            from[q]=p;
            visited[q]=true;
            Q.push(q);
        }
    }
    if(from[sink]==-1) return 0;
    int max_cap = MAX_CAP;
    int q = sink;
    while (from[q]!=-1) {
        int p = from[q];
        max_cap = min(max_cap, cap[p][q]);
        q = p;
    }
    q = sink;
    while (from[q]!=-1) {
        int p = from[q];
        cap[p][q]-=max_cap;
        cap[q][p]+=max_cap;
        q = p;
    }
    return max_cap;
}

int max_flow(int sink, int source) {
    int res =0;
    while(true) {
        int flow = find_path(sink, source);
        if(flow==0)break;
        res += flow;
    }

    return res;
}

int main()
{
    int n,m;
    cin >>n>>m;
    int P[n];
    int K[n];
    int C[n];
    int task[n];
    int total_task =0;
    for(int i=0;i<n;i++){
        cin >> P[i]>>K[i]>>C[i];
        total_task+=C[i];
    }
    int source = add_vertex();
    int sink = add_vertex();
    for(int i=0;i<n;i++){
        task[i]=add_vertex();
        add_edge(task[i], sink, C[i]);
    }
    vector<pair<int,int>> events;
    for(int i=0;i<n;i++) {
        events.push_back(make_pair(P[i], i+1));
        events.push_back(make_pair(K[i], -i-1));
    }
    sort(events.begin(), events.end());
    set<int>open;
    int prev =0;
    for(auto it = events.begin();it!=events.end();++it) {
        int t = it->first;
        int id = it->second;
        int dt = t - prev;
        int oc = open.size();
        if(oc > 0 && dt >0) {
            //cout << "SEGMENT "<<prev<<" - "<<t<<": ";
            int processed = min(m, oc) * dt;
            int pv = add_vertex();
          //  cout <<"  total processed: "<<processed<<endl;
            add_edge(source, pv, processed);
            for(auto it = open.begin();it!=open.end();++it) {
                add_edge(pv, task[*it], dt);
              //  cout <<"  task "<<*it<<endl;
            }
        }
        if(id>0) {
            id--;
            open.insert(id);
        } else {
            id = -id - 1;
            open.erase(id);
        }
        prev = t;
    }
    int flow = max_flow(sink, source);
    if(flow==total_task)cout <<"TAK\n";
    else cout <<"NIE\n";
    return 0;
}