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
// Zadanie: Szeregowanie zadan [B]
// Autor: Arkadiusz Roussau

#include <algorithm>
#include <iostream>
#include <utility>
#include <cstdio>
#include <queue>

using namespace std;

const int MAX_CZAS = 1000002;
const int MAX_PROCESOW = 102;
bool TAB[MAX_CZAS][MAX_PROCESOW];
int LICZNIK[MAX_CZAS], KOSZT[MAX_PROCESOW], CZAS[MAX_PROCESOW], p, k, c, max_k = -1, swob;
int zadania, procesory;
pair<int, int> para;

int main() {
    scanf("%d %d", &zadania, &procesory);

    for (int i = 0; i < zadania; ++i) {
        scanf("%d %d %d", &p, &k, &c);

        for (int j = p; j < k; ++j) {
            TAB[j][i] = true;
            LICZNIK[j]++;
        }

        CZAS[i] = k - p;
        KOSZT[i] = c;
        max_k = max(max_k, k);
    }

    for (int i = 0; i < max_k; ++i) {
        if (LICZNIK[i] <= procesory) {
            for (int j = 0; j < zadania; ++j) {
                if(TAB[i][j]) {
                    KOSZT[j]--;
                    CZAS[j]--;
                }
            }
        }
    }

    for (int i = 0; i < max_k; ++i) {
        if (LICZNIK[i] > procesory) {
            priority_queue< pair<int , int> > Q;

            for (int j = 0; j < zadania; ++j) {
                if ((TAB[i][j]) && (0 < KOSZT[j])) {
                    CZAS[j]--;
                    swob = -(CZAS[j] - KOSZT[j]);
                    
                    Q.push(make_pair(swob, j));
                }
            }
            
            for (int j = 0; j < procesory; ++j) {
                if(Q.empty()) {
                    break;
                }
                
                KOSZT[Q.top().second]--;
                Q.pop();
            }
        }
    }
    
    for (int i = 0; i < zadania; ++i) {
        if (0 < KOSZT[i]) {
            printf("NIE");
            
            return 0;
        }
    }
    
    printf("TAK");
    
    return 0;
}