Submission #1185018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185018		bkws	Jobs (BOI24_jobs)	Java	0 / 100	56 ms	11596 KiB

Main

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

public class Main {
    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static int readInt() throws IOException {
        return Integer.parseInt(reader.readLine());
    }

    public static int[] readIntArr() throws IOException {
        return Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    public static long readLong() throws IOException {
        return Long.parseLong(reader.readLine());
    }

    public static long[] readLongs() throws IOException {
        return Arrays.stream(reader.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
    }

    public static <T> void print(T str) {
        System.out.print(str);
    }

    public static void main(String[] args) throws IOException {
        int n = 1; // readInt();
        for (int i = 1; i <= n; i++) {
            solve();
        }
    }

    public static void solve() throws IOException {
        int[] Ns = readIntArr();
        int nJobs = Ns[0]; int initMoney = Ns[0];

        int[] profitMap = new int[nJobs+1]; profitMap[0] = 0;
        ArrayList<Integer>[] adj = new ArrayList[nJobs+1];
        adj[0] = new ArrayList<>();

        for (int i = 1; i <= nJobs; i++) {
            adj[i] = new ArrayList<>();
            int[] xp = readIntArr();
            profitMap[i] = xp[0];
            //xp[1] < i
            adj[xp[1]].add(i);
        }
        print(maxProfit(0,initMoney,profitMap,adj));
    }

    public static int maxProfit(int job, int money, int[] profitMap, ArrayList<Integer>[] adj) {
//        System.out.println("get max profit: job nr "+job+" entry money "+money);
        if (adj[job].isEmpty()) { return profitMap[job]; }
        HashMap<Integer,Integer> maxProfitMap = new HashMap<>();
        for (int preJob : adj[job]) {
            maxProfitMap.put(preJob,maxProfit(preJob, money + profitMap[job], profitMap, adj));
        }
        adj[job].sort(Comparator.comparingInt(o -> -profitMap[o]));
        int r = 0;
        for (int j : adj[job]) {
            if (money + profitMap[j] < 0) { break; }
            int maxProfit = maxProfitMap.get(j);
            if (maxProfit < 0) { continue; }
            r += maxProfit; money += maxProfit;
        }
        return r + profitMap[job];
    }
}

Compilation message (stderr)

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

=======

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