제출 #1141235

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

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 1e5;
vector<int> adj[N];

int dfs(int node, vector<pair<int, int>>& job, vector<bool>& vis) {
    vis[node] = true;
    int sum = job[node].first;
    for (auto i : adj[node]) {
        if (!vis[i]) {
            sum += dfs(i, job, vis);
        }
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, s;
    cin >> n >> s;

    vector<pair<int, int>> job(n);
    for (int i = 0; i < n; ++i) {
        cin >> job[i].first >> job[i].second;
        if (job[i].second != 0) {
            adj[i].push_back(job[i].second - 1);
        }
    }

    vector<int> dp(n, 0);
    vector<bool> vis(n, false);

    dp[0] = max(job[0].first + s, s);
    vis[0] = dp[0] == job[0].first + s;

    for (int i = 1; i < n; ++i) {
        if (job[i].second == 0) {
            dp[i] = max(dp[i - 1], dp[i - 1] + job[i].first);
        } else {
            int parent = job[i].second - 1;
            if (!vis[parent]) {
                dp[i] = dp[i - 1] + dfs(parent, job, vis);
            }
            dp[i] = max(dp[i - 1], dp[i] + job[i].first);
        }
        vis[i] = dp[i] != dp[i - 1];
    }

    cout << dp[n - 1] - s << endl;
    return 0;
}

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