AtCoder. 011 Gravy Jobs(6)

import java.util.*;
import java.io.*;
//1. In schedule, the job which deadline is the longest have to go at last
//-> Applying 1 recursively, ideal schedule is sorted in ascending order of deadline
public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int n = Integer.parseInt(br.readLine());
    long[] dp;
    LinkedList<int[]> info = new LinkedList<>();
    for(int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      int[] temp = new int[3];
      for(int j = 0; j < 3; j++) temp[j] = Integer.parseInt(st.nextToken());
      info.add(temp);
    }
    info.sort((l, r) -> l[0] - r[0]);
    int range = 0;
    dp = new long[info.get(n - 1)[0] + 1];
    for(int i = 0; i < n; i++) {
      int[] newInfo = info.get(i);
      for(int j = newInfo[0]; j >=  newInfo[1]; j--) {
        fillArr(dp, j, Math.max(dp[j], dp[j - newInfo[1]] + newInfo[2]));
      }
    }
    for(long e: dp ) System.out.print(e + " ");
    System.out.println(dp[dp.length - 1]);
  }

  static void fillArr(long[] arr, int idx, long v) {
    for(int i = idx; i < arr.length; i++) {
      if(v <= arr[i]) return;
      arr[i] = v;
    }
  }
}