제출 #1141216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141216		harry_tm_18	Jobs (BOI24_jobs)	C++17	0 / 100	12 ms	14516 KiB

Main

#include <bits/stdc++.h>

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;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31