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
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>



using namespace std;

int main(int argc, char *argv[])
{

    std::ios::sync_with_stdio(false);

    vector <pair<int, int>> pozostalo_czasu; // ile pozostalo czasu, ile jeszcze do zrobienia

    vector <tuple<int, int, int> > wejscie;

    int n,m;

    cin>>n>>m;

    if (n<=m) { // nie wiecej zadań niz procesorów, spałniają warunki
        cout<<"TAK"<<endl;
        return 0;
    }


    wejscie.reserve(n);
    for (int i=0;i<n;i++)
    {
        int p,k,c;
        cin>>p>>k>>c;
        wejscie.push_back( make_tuple(p,k,c));
    }

    sort ( begin(wejscie), end(wejscie) );

    int t;

    t = get<0>(wejscie[0]);

    auto iter_wej = begin(wejscie);

    while( (iter_wej!=end(wejscie)) || ( !pozostalo_czasu.empty() ))
    {
        bool cos_doszlo = false;
        while ((iter_wej!=end(wejscie)) && ( t == get<0>(*iter_wej)))
        {
            int p,k,c;
            tie(p,k,c) = *iter_wej;
            iter_wej++;
            cos_doszlo = true;

            pozostalo_czasu.push_back( make_pair((k-p) - c ,c) );

        }
        if (cos_doszlo)
            sort (begin(pozostalo_czasu), end(pozostalo_czasu));


        for(auto it = begin(pozostalo_czasu); it!=end(pozostalo_czasu); it++){

            if ( it - begin(pozostalo_czasu) < m )
                it->second--;
            else
                it->first--;

            if ((it->first <0) && (it->second>0) )
            {
                cout<<"NIE"<<endl;
                return 0;
            }
        }

        if( ( pozostalo_czasu.size()>m)  && // bądą oczekujące procesy...
                (pozostalo_czasu[m].first < pozostalo_czasu[m-1].first ))
        {
            auto a = lower_bound( pozostalo_czasu.begin(), pozostalo_czasu.begin()+m,
                                  make_pair(pozostalo_czasu[m-1].first, 0 ));
            auto b = upper_bound( pozostalo_czasu.begin()+m, pozostalo_czasu.end(),
                                  make_pair(pozostalo_czasu[m].first, numeric_limits<int>::max() ));
            reverse( a,b );
       }

        pozostalo_czasu.erase( std::remove_if( pozostalo_czasu.begin(), pozostalo_czasu.end(),
                                [](pair<int, int> x){ return x.second==0;}
                                ), pozostalo_czasu.end() );

        if ((iter_wej==end(wejscie)) && (pozostalo_czasu.size()<=m)) {//nie wiecej  zadań niż procesorów
            cout<<" TAK"<<endl;
            return 0;
        }

        t++;
    }



    cout << "TAK" << endl;
    return 0;
}