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
#include<bits/stdc++.h>
using namespace std;

#define temp first
#define litres second
using Bottles = vector<pair<int, int>>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while(T--) {
        int n; cin >> n;
        Bottles start, dest;
        long long startsum = 0, destsum = 0;
        for(int i = 0; i < n; i++) {
            int l, a, b;
            cin >> l >> a >> b;
            startsum += (long long) a * l;
            destsum += (long long) b * l;
            start.emplace_back(a, l);
            dest.emplace_back(b, l);
        }

        sort(begin(start), end(start));
        sort(begin(dest), end(dest));

        auto check = [&](long long sa, long long sb, const Bottles &va, const Bottles &vb) {
            if(sa != sb) return false;
            auto n = va.size();
            assert(n == vb.size());

            long long sum = 0, quantity = 0;
            for(size_t i = 0, j = 0, taken = 0; i < n; i++) {
                while(j < n and quantity < vb[i].litres) {
                    auto no = min(vb[i].litres - quantity, (long long)(va[j].litres - taken));
                    taken += no;
                    sum += (long long) no * va[j].temp;
                    quantity += no;
                    if(taken == va[j].litres) 
                        j += 1, taken = 0;
                }
                
                assert(quantity >= vb[i].litres);
                if(sum > vb[i].temp * quantity)
                    return false;
                sum -= (long long) vb[i].temp * vb[i].litres;
                quantity -= vb[i].litres;
            }
            return true;
        };

        auto transform = [&](Bottles &v) {
            reverse(begin(v), end(v));
            for(auto &x : v)
                x.temp *= -1;
        };

        auto pref = check(startsum, destsum, start, dest);
        transform(start), transform(dest);
        auto suf = check(-startsum, -destsum, start, dest);

        cout << (pref and suf ? "TAK\n" : "NIE\n");
    }
}