Submission #1185806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185806		bkws	Jobs (BOI24_jobs)	Java	0 / 100	2096 ms	249748 KiB

Main

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

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 String indent(int n) {
        var r = "";
        for (int i = 0; i < n; i++) {
            r = "   " + r;
        }
        return  r;
    }

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

    public static TreeMap<Long,Long>[] dp;
    public static long[] profitMap;
    public static ArrayList<Integer>[] adj;
    public static void solve() throws IOException {
        long[] Ns = readLongs();
        int nJobs = (int)Ns[0]; long initMoney = Ns[1];

        profitMap = new long[nJobs+1];
        profitMap[0] = 0;
        adj = new ArrayList[nJobs+1];
        adj[0] = new ArrayList<>();
        dp = new TreeMap[nJobs+1];
        dp[0] = new TreeMap<>();

        for (int i = 1; i <= nJobs; i++) {
            dp[i] = new TreeMap<>();
            adj[i] = new ArrayList<>();
            int[] xp = readIntArr();
            profitMap[i] = xp[0];
            //PRE xp[1] < i
            adj[xp[1]].add(i);
        }

        System.out.println(maxProfit(0,initMoney,0));
    }
    public static long maxProfit(int job, long money,int level) {
        var floor = dp[job].floorEntry(money);
        var ceil = dp[job].ceilingEntry(money);
        if (floor != null && ceil != null && floor.getValue() == ceil.getValue()) {
            return floor.getValue();
        }
        if (adj[job].isEmpty()) {
            dp[job].put(money,Math.max(profitMap[job],0));
            return Math.max(profitMap[job],0);
        }
        HashMap<Integer,Long> maxProfitMap = new HashMap<>();
        long sumProfit = 0;
        int c = 0;
        while (true) {
            c++;
            var oldMaxProfitMap = (HashMap<Integer,Long>)maxProfitMap.clone();
            for (int j : adj[job]) {
                if (!oldMaxProfitMap.containsKey(j)) { oldMaxProfitMap.put(j,0L); }
                if (money + profitMap[job] + profitMap[j] < 0) { maxProfitMap.put(j,0L); continue; }
                maxProfitMap.put(j, maxProfit(j, money + profitMap[job] - Math.max(oldMaxProfitMap.get(j),0), level + 1));
            }
            adj[job].sort(Comparator.comparingLong(o -> -maxProfitMap.get(o)));
            var gaining = false;
            for (int i = 0; i < adj[job].size(); i++) {
                int j = adj[job].get(i);
                if (money + profitMap[job] + profitMap[j] < 0) { continue; } // - oldMaxProfitMap.get(j) should not change the sign
                long gain = maxProfitMap.get(j) - Math.max(oldMaxProfitMap.get(j),0);
                if (gain == 0 || maxProfitMap.get(j) < 0) { continue; }
                gaining = true;
                sumProfit += gain;
                money += gain;
            }
            if (!gaining) { break; }
        }
        dp[job].put(money, sumProfit + profitMap[job]);
        return sumProfit + 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