제출 #1185136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185136		bkws	Jobs (BOI24_jobs)	Java	0 / 100	2078 ms	235500 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 {
        long[] Ns = readLongs();
        int nJobs = (int)Ns[0]; long initMoney = Ns[0];

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

        for (int i = 1; i <= nJobs; i++) {
            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,profitMap,adj));
    }

    public static long maxProfit(int job, long money, long[] profitMap, ArrayList<Integer>[] adj) {
        if (adj[job].isEmpty()) { return Math.max(profitMap[job],0); }
        HashMap<Integer,Long> maxProfitMap = new HashMap<>();
        long sumProfit = 0;
        while (true) {
            var oldMaxProfitMap = (HashMap<Integer,Long>)maxProfitMap.clone();
            for (int preJob : adj[job]) {
                maxProfitMap.put(preJob,maxProfit(preJob, money + profitMap[job], profitMap, adj));
            }
            adj[job].sort(Comparator.comparingLong(o -> -maxProfitMap.get(o)+profitMap[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; }
                long gain = maxProfitMap.get(j)
                        - (oldMaxProfitMap.containsKey(j) ? oldMaxProfitMap.get(j) : 0);
                if (gain <= 0) { continue; }
                gaining = true;
                sumProfit += gain;
                money += gain;
            }
            if (!gaining) { break; }
        }
        return sumProfit + profitMap[job];
    }
}

컴파일 시 표준 에러 (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