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

int n, m;
int minP = 1000001, maxK = 0;
int p, k, c;
bool sukces = true;

multiset<tuple<double, int, int, int>> przedzialy;
multiset<tuple<int, int, int>> przedzialy2;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d%d",&p,&k,&c);
    if (p < minP) minP = p;
    if (k > maxK) maxK = k;
    przedzialy.insert(make_tuple(-(double)c/(double)(k-p), p, k, c));
    przedzialy2.insert(make_tuple(p, k, c));
  }
  if ( m >= n) {printf("TAK\n"); return 0;}
  else {
    for (int i = minP; i <= maxK; ++i) {
      int k = 0;
      for (auto it=przedzialy.begin(); it!=przedzialy.end();) {
        if (get<1>(*it) > i) break; //już jestem za daleko
        if (get<2>(*it) > i) {
         auto it2 = it++;
         tuple<double, int, int, int> x (-(double)get<3>(*it2)/(double)(get<2>(*it2) - (i + 1)), i + 1, get<2>(*it2), get<3>(*it2));
         if (k++ < m) {
           get<3>(x)--;
           get<0>(x) = -(double)get<3>(x)/(double)(get<2>(x) - get<1>(x));
         }
         przedzialy.erase(it2);
         if(get<3>(x) > 0) przedzialy.insert(x);
        }
        else {
          it++;
        }
      }
      for (auto x : przedzialy) {
        if (get<2>(x) - get<1>(x) < get<3>(x)) {
          sukces = false;
          break;
        }
      }
      if(!sukces) break;
    }
    if(sukces)
      printf("TAK\n");
    else {
      for (int i = minP; i <= maxK; ++i) {
        int k = 0;
        for (auto it=przedzialy2.begin(); it!=przedzialy2.end();) {
          if (get<0>(*it) > i) break; //już jestem za daleko
          if (get<1>(*it) > i) {
           //  ~k++; 
           //ustawić 
           auto it2 = it++;
           tuple<int, int, int> x (i + 1, get<1>(*it2), get<2>(*it2));
           if (k++ < m) get<2>(x)--;
           przedzialy2.erase(it2);
           if(get<2>(x) > 0) przedzialy2.insert(x);
          }
          else {
            it++;
          }
        }
        for (auto x : przedzialy2) {
          if (get<1>(x) - get<0>(x) < get<2>(x)) {
            printf("NIE\n"); return 0;
          }
        }
      }
    printf("TAK\n");
    }
  }
  return 0;
}