Submission #70771363

---

Source Code Expand

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        
        int[] weight = new int[n];
        long[] headHappiness = new long[n];
        long[] bodyHappiness = new long[n];
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            weight[i] = Integer.parseInt(st.nextToken());
            headHappiness[i] = Long.parseLong(st.nextToken());
            bodyHappiness[i] = Long.parseLong(st.nextToken());
        }
        
        System.out.println(solve(n, weight, headHappiness, bodyHappiness));
    }
    
    public static long solve(int n, int[] weight, long[] headHappiness, long[] bodyHappiness) {
        int totalWeight = 0;
        for (int w : weight) {
            totalWeight += w;
        }
        
        int maxHeadWeight = totalWeight / 2;
        
        long[] dp = new long[maxHeadWeight + 1];
        long[] newDp = new long[maxHeadWeight + 1];
        
        Arrays.fill(dp, Long.MIN_VALUE);
        dp[0] = 0;
        
        for (int i = 0; i < n; i++) {
            Arrays.fill(newDp, Long.MIN_VALUE);
            
            for (int j = 0; j <= maxHeadWeight; j++) {
                if (dp[j] == Long.MIN_VALUE) continue;
                
                // Option 1: Attach to body
                newDp[j] = Math.max(newDp[j], dp[j] + bodyHappiness[i]);
                
                if (j + weight[i] <= maxHeadWeight) {
                    newDp[j + weight[i]] = Math.max(
                        newDp[j + weight[i]], 
                        dp[j] + headHappiness[i]
                    );
                }
            }
            
            long[] temp = dp;
            dp = newDp;
            newDp = temp;
        }
        
        long maxHappiness = 0;
        for (int j = 0; j <= maxHeadWeight; j++) {
            if (dp[j] != Long.MIN_VALUE) {
                maxHappiness = Math.max(maxHappiness, dp[j]);
            }
        }
        
        return maxHappiness;
    }
}

Submission Info

Judge Result