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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int q;
    cin >> q;
    while(q--){
        vector<pll> x;
        vector<pll> y;
        int n;
        cin >> n;
        ll sa = 0;
        ll sb = 0;
        ll l, a, b;
        for(int i = 0; i < n;i++){
            cin >> l >> a >> b;
            y.push_back({b,l});
            x.push_back({a,l});
            sa+=l*a;
            sb+=l*b;
        }
        if(sa!=sb){
            cout << "NIE\n";
            continue;
        }
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        if(y[n-1]>x[n-1] || y[0]<x[0]){
            cout << "NIE\n";
            continue;
        }
        int ido = x.size()-1;
        int idt = y.size()-1;
        ll sp = 0;
        ll lt = 0;
        bool odp = false;
        while(ido>=0 || idt>=0){
            //cout << ido << " " << x[ido].first << " " << idt << " " << y[idt].first << " " << lt << " " << sp << endl;
            if(idt<0){
                sp+=x[ido].first*x[ido].second;
                lt+=x[ido].second;
                ido--;
                continue;
            }
            if(ido<0){
                if(lt>= y[idt].second && sp >= y[idt].second*y[idt].first){
                    sp-= y[idt].second*y[idt].first;
                    lt-= y[idt].second;
                    idt--;
                    continue;
                }
                cout << "NIE\n";
                odp=true;
                break;
            }
            if(x[ido].first>=y[idt].first){
                sp+=x[ido].first*x[ido].second;
                lt+=x[ido].second;
                ido--;
            }
            else{
                if((lt <= 0 && sp <= 0) || (lt>=y[idt].second && sp<y[idt].second*y[idt].first)){
                    cout << "NIE\n";
                    odp=true;
                    break;
                }
                if(lt>= y[idt].second && sp >= y[idt].second*y[idt].first){
                    lt-=y[idt].second;
                    sp-=y[idt].second*y[idt].first;
                    idt--;
                }
                else{
                    sp+=x[ido].first*x[ido].second;
                    lt+=x[ido].second;
                    ido--;
                }
            }
        }
        if(odp==false)
            cout << "TAK\n";
    }

}