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

//sposob uzycia:
//ustawic nn, vS, vT, wstawic krawedzie odpalic while(Dinic());
 
const long long inf = 1e18;
int inf2 = 2e9;
 
const int M = 50000 + 7; //max liczba krawedzi, UWAGA - LICZYMY KAZDA KRAWEDZ DWA RAZY, JEZELI GRAF JEST NIESKIEROWANY TO CZTERY
const int N = 350 + 7; //max liczba wierzcholkow, 7 jest konieczna
vector <int> G[N]; //siec
int nG[M]; //graf warstwowy, zapisany w jednowymiarowej tablicy
int nGS[N]; //gdzie zaczyna sie i-ty wierzcholek w nG 
int nGK[N]; //gdzie konczy sie i-ty wierzcholek w nG
int odl[N]; //odlegosc i-tego wierzcholka od zrodla (do BFSa)
int qq[N]; //kolejka do BFSa
int ev[M]; //do jakiego wierzcholka prowadzi i-ta krawedz
int cap[M]; //przepustowosc w residualnym (rzeczywisty przeplyw jest rowny ocap_i - cap_i (ocap to oryginalna przepustowosc)
int edge_id = 0; 
int vS, vT; //numery zrodla i ujscia
int nn; //ile jest wierzcholkow w sieci (numery wierzcholkow musza byc od 1 do nn)
long long wynik = 0;
 
void add_edge(int a, int b, int c, bool tam = 1) {
	ev[edge_id] = b;
	cap[edge_id] = c;
	G[a].push_back(edge_id);
	edge_id++;
	if(tam) add_edge(b, a, 0, 0); 
}
 
long long dinic_dfs(int v, long long flo = inf) { //puszcza przeplyw blokujacy
	if(v == vT) return flo;
	long long res = 0;
	int j = nGK[v];
	while(j >= nGS[v] && flo > 0) {
		long long ile = dinic_dfs(ev[nG[j]], min(flo, (long long) cap[nG[j]]));
		if(ile == 0) j--;
		else {
			res += ile;
			flo -= ile;
			cap[nG[j]] -= ile;
			cap[(nG[j]) ^ 1] += ile;
			if(cap[nG[j]] == 0) j--;
		}
	}
	nGK[v] = j;
	return res;
}
 
bool Dinic() { //funkcja znajduje przeplyw blokujacy lub zwraca 0 gdy przeplyw jest juz maksymalny
	for(int i = 1; i <= nn; ++i) odl[i] = inf2;
	odl[vS] = 0;
	qq[0] = vS;
	int qlen = 1;
	
	for(int i = 0; i < qlen; ++i) {
		int v = qq[i];
		for(auto j : G[v]) {
			if(odl[ev[j]] == inf2 && cap[j] > 0) {
				odl[ev[j]] = odl[v] + 1;
				qq[qlen++] = ev[j];
			}
		}
	}
	
	if(odl[vT] == inf2) return 0;
	
	int poz = 0;
	for(int i = 1; i <= nn; ++i) {
		nGS[i] = poz;
		for(auto j : G[i]) {
			if(cap[j] > 0 && odl[i] + 1 == odl[ev[j]]) nG[poz++] = j;
		}
		nGK[i] = poz - 1;
	}
	
	wynik += dinic_dfs(vS);
	return 1;
}

int n, m;
int p[107];
int k[107];
int c[107];

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	vector <pair <int, int> > evs;
	
	for(int i = 1; i <= n; ++i) {
		cin >> p[i] >> k[i] >> c[i];
		p[i]++;
		evs.push_back(make_pair(p[i], i));
		evs.push_back(make_pair(k[i] + 1, -i));
	}
	
	sort(evs.begin(), evs.end());
	
	nn = 1;
	vS = 1;
	vector <int> pro;
	int lt = -1;
	
	for(auto u : evs) {
		if(u.first != lt) {
			if(lt != -1) {
				nn++;
				add_edge(1, nn, m * (u.first - lt));
			}
			lt = u.first;
		}
	}
	
	int cnn = nn;
	lt = -1;
	nn = 1;
	
	for(auto u : evs) {
		if(u.first != lt) {
			if(lt != -1) {
				nn++;
				for(auto v : pro) add_edge(nn, cnn + v, u.first - lt);
			}
			lt = u.first;
		}
		if(u.second > 0) pro.push_back(u.second);
		else pro.erase(find(pro.begin(), pro.end(), -u.second));
	}
	
	for(int i = 1; i <= n; ++i) add_edge(cnn + i, cnn + n + 1, c[i]);
	nn = cnn + n + 1;
	vT = nn;
	
	while(Dinic());
	
	for(int i = 1; i <= n; ++i) wynik -= c[i];
	if(wynik == 0) cout << "TAK\n";
	else cout << "NIE\n";
	return 0;
}