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 // Marcin Knapik Potyczki Algorytmiczne, dzień 2, Zadanie "Herbata"[B] // złożoność O(n log n) #include using namespace std; #define rall(s) s.rbegin(), s.rend() #define f first #define s second #define ll long long #define pb push_back int q, n; void solve(){ cin >> q; while(q--){ cin >> n; vector > jest; vector > ma_byc; ll suma = 0; for(int i = 0; i < n; i++){ int a, b, c; cin >> a >> b >> c; suma += a; jest.pb({b, a}); ma_byc.pb({c, a}); } sort(rall(jest)); sort(rall(ma_byc)); ll bilans = 0; bool ok = true; int id_jest = -1; int id_ma_byc = -1; ll kon_jest = -1; ll kon_ma_byc = -1; ll poz = 0; while(poz < suma){ if(poz > kon_jest){ id_jest++; kon_jest += jest[id_jest].s; } if(poz > kon_ma_byc){ id_ma_byc++; kon_ma_byc += ma_byc[id_ma_byc].s; } bilans += (ll)(jest[id_jest].f - ma_byc[id_ma_byc].f) * (min(kon_ma_byc, kon_jest)-poz+1); poz = min(kon_ma_byc, kon_jest)+1; if(bilans < 0) ok = false; } if(bilans != 0) ok = false; cout << (ok ? "TAK\n" : "NIE\n"); } } int main(){ ios::sync_with_stdio(0); cin.tie(0); solve(); }