#include <iostream>
using namespace std;

void calculateNeed(int **need, int **max, int **allocated, int n, int m) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            need[i][j] = max[i][j] - allocated[i][j];
        }
    }
}

bool isSafe(int *processes, int *available, int **max, int **allocated, int n, int m) {
    int **need = new int*[n];
    for (int i = 0; i < n; i++) {
        need[i] = new int[m];
    }
    calculateNeed(need, max, allocated, n, m);

    bool *finish = new bool[n]();
    int *safeSequence = new int[n];
    int *work = new int[m];

    for (int i = 0; i < m; i++) {
        work[i] = available[i];
    }

    int count = 0;
    while (count < n) {
        bool found = false;
        for (int p = 0; p < n; p++) {
            if (!finish[p]) {
                bool canAllocate = true;
                for (int j = 0; j < m; j++) {
                    if (need[p][j] > work[j]) {
                        canAllocate = false;
                        break;
                    }
                }
                if (canAllocate) {
                    for (int j = 0; j < m; j++) {
                        work[j] += allocated[p][j];
                    }
                    safeSequence[count++] = p;
                    finish[p] = true;
                    found = true;
                }
            }
        }

        if (!found) {
            cout << "System is not in a safe state. Deadlock occurs." << endl;

            // Free dynamically allocated memory
            for (int i = 0; i < n; i++) {
                delete[] need[i];
            }
            delete[] need;
            delete[] finish;
            delete[] safeSequence;
            delete[] work;

            return false;
        }
    }

    cout << "System is in a safe state.\nSafe sequence is: ";
    for (int i = 0; i < n; i++) {
        cout << safeSequence[i] << " ";
    }
    cout << endl;

    // Free dynamically allocated memory
    for (int i = 0; i < n; i++) {
        delete[] need[i];
    }
    delete[] need;
    delete[] finish;
    delete[] safeSequence;
    delete[] work;

    return true;
}

int main() {
    int n, m;

    cout << "Enter the number of processes: ";
    cin >> n;

    cout << "Enter the number of resource types: ";
    cin >> m;

    int *processes = new int[n];
    for (int i = 0; i < n; i++) {
        processes[i] = i;
    }

    int *available = new int[m];
    cout << "Enter the available resources for each type: ";
    for (int i = 0; i < m; i++) {
        cin >> available[i];
    }

    int **max = new int*[n];
    for (int i = 0; i < n; i++) {
        max[i] = new int[m];
    }
    cout << "Enter the maximum resource matrix:\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> max[i][j];
        }
    }

    int **allocated = new int*[n];
    for (int i = 0; i < n; i++) {
        allocated[i] = new int[m];
    }
    cout << "Enter the allocated resource matrix:\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> allocated[i][j];
        }
    }

    isSafe(processes, available, max, allocated, n, m);

    // Free dynamically allocated memory
    delete[] processes;
    delete[] available;
    for (int i = 0; i < n; i++) {
        delete[] max[i];
        delete[] allocated[i];
    }
    delete[] max;
    delete[] allocated;

    return 0;
}