Submission #1141213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141213		harry_tm_18	Jobs (BOI24_jobs)	C++20	Compilation error	0 ms	0 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Job {
    int profit;
    int prerequisite;
};

int main() {
    int N, s;
    cin >> N >> s;

    vector<Job> jobs(N + 1); // Jobs are indexed from 1 to N
    vector<vector<int>> adj(N + 1); // Adjacency list for dependencies
    vector<int> inDegree(N + 1, 0); // In-degree for topological sorting

    for (int i = 1; i <= N; i++) {
        cin >> jobs[i].profit >> jobs[i].prerequisite;
        if (jobs[i].prerequisite != 0) {
            adj[jobs[i].prerequisite].push_back(i);
            inDegree[i]++;
        }
    }

    // Topological sort using Kahn's algorithm
    queue<int> q;
    vector<int> topoOrder;

    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        topoOrder.push_back(cur);

        for (int neighbor : adj[cur]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // DP to calculate the maximum profit
    vector<int> dp(N + 1, INT_MIN); // dp[i] = max profit achievable ending with job i
    dp[0] = s; // Initial money

    for (int job : topoOrder) {
        if (dp[jobs[job].prerequisite] >= 0) { // Ensure prerequisite job can be completed
            dp[job] = max(dp[job], dp[jobs[job].prerequisite] + jobs[job].profit);
        }
    }

    // Find the maximum profit achievable
    int maxProfit = 0;
    for (int i = 1; i <= N; i++) {
        maxProfit = max(maxProfit, dp[i]);
    }

    cout << maxProfit - s << endl; // Subtract initial money to get the profit

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:27: error: 'INT_MIN' was not declared in this scope
   53 |     vector<int> dp(N + 1, INT_MIN); // dp[i] = max profit achievable ending with job i
      |                           ^~~~~~~
Main.cpp:5:1: note: 'INT_MIN' is defined in header '<climits>'; did you forget to '#include <climits>'?
    4 | #include <algorithm>
  +++ |+#include <climits>
    5 |