题解 | #中世纪的商路#

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <map>

using namespace std;

struct Trade {
    int start;
    int end;
    int fleet;
    int profit;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string line;
    vector<int> starts, ends, fleets, profits;
    int val;

    getline(cin, line); stringstream ss_starts(line);
    while (ss_starts >> val) starts.push_back(val);

    getline(cin, line); stringstream ss_ends(line);
    while (ss_ends >> val) ends.push_back(val);

    getline(cin, line); stringstream ss_fleets(line);
    while (ss_fleets >> val) fleets.push_back(val);

    getline(cin, line); stringstream ss_profits(line);
    while (ss_profits >> val) profits.push_back(val);

    int max_fleet;
    cin >> max_fleet;

    map<int, vector<Trade>> trades_ending_at;
    int max_time = 0;
    for (size_t i = 0; i < starts.size(); ++i) {
        if (fleets[i] <= max_fleet) {
            trades_ending_at[ends[i]].push_back({starts[i], ends[i], fleets[i], profits[i]});
            max_time = max(max_time, ends[i]);
        }
    }

    vector<vector<long long>> dp(max_time + 1, vector<long long>(max_fleet + 1, 0));

    for (int t = 1; t <= max_time; ++t) {
        for (int w = 0; w <= max_fleet; ++w) {
            dp[t][w] = dp[t - 1][w];
        }

        if (trades_ending_at.count(t)) {
            for (const auto& trade : trades_ending_at[t]) {
                int start_time = trade.start;
                int fleet_cost = trade.fleet;
                int profit_val = trade.profit;

                for (int w = max_fleet; w >= fleet_cost; --w) {
                    dp[t][w] = max(dp[t][w], dp[start_time][w - fleet_cost] + profit_val);
                }
            }
        }
    }

    long long max_profit = 0;
    for (int w = 0; w <= max_fleet; ++w) {
        max_profit = max(max_profit, dp[max_time][w]);
    }

    cout << max_profit << endl;

    return 0;
}

import java.util.*;

class Trade {
    int start, end, fleet, profit;

    public Trade(int start, int end, int fleet, int profit) {
        this.start = start;
        this.end = end;
        this.fleet = fleet;
        this.profit = profit;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String[] startStrs = sc.nextLine().split(" ");
        String[] endStrs = sc.nextLine().split(" ");
        String[] fleetStrs = sc.nextLine().split(" ");
        String[] profitStrs = sc.nextLine().split(" ");
        int maxFleet = Integer.parseInt(sc.nextLine());

        Map<Integer, List<Trade>> tradesEndingAt = new HashMap<>();
        int maxTime = 0;

        for (int i = 0; i < startStrs.length; i++) {
            if (startStrs[i].isEmpty()) continue;
            int fleet = Integer.parseInt(fleetStrs[i]);
            if (fleet <= maxFleet) {
                int start = Integer.parseInt(startStrs[i]);
                int end = Integer.parseInt(endStrs[i]);
                int profit = Integer.parseInt(profitStrs[i]);
                
                tradesEndingAt.putIfAbsent(end, new ArrayList<>());
                tradesEndingAt.get(end).add(new Trade(start, end, fleet, profit));
                maxTime = Math.max(maxTime, end);
            }
        }

        long[][] dp = new long[maxTime + 1][maxFleet + 1];

        for (int t = 1; t <= maxTime; t++) {
            for (int w = 0; w <= maxFleet; w++) {
                dp[t][w] = dp[t - 1][w];
            }

            if (tradesEndingAt.containsKey(t)) {
                for (Trade trade : tradesEndingAt.get(t)) {
                    int startTime = trade.start;
                    int fleetCost = trade.fleet;
                    int profitVal = trade.profit;

                    for (int w = maxFleet; w >= fleetCost; w--) {
                        dp[t][w] = Math.max(dp[t][w], dp[startTime][w - fleetCost] + profitVal);
                    }
                }
            }
        }

        long maxProfit = 0;
        for (int w = 0; w <= maxFleet; w++) {
            maxProfit = Math.max(maxProfit, dp[maxTime][w]);
        }

        System.out.println(maxProfit);
    }
}

def solve():
    starts = list(map(int, input().split()))
    ends = list(map(int, input().split()))
    fleets = list(map(int, input().split()))
    profits = list(map(int, input().split()))
    max_fleet = int(input())

    trades_ending_at = {}
    max_time = 0
    for i in range(len(starts)):
        if fleets[i] <= max_fleet:
            end_time = ends[i]
            if end_time not in trades_ending_at:
                trades_ending_at[end_time] = []
            trades_ending_at[end_time].append((starts[i], fleets[i], profits[i]))
            max_time = max(max_time, end_time)

    if max_time == 0:
        print(0)
        return

    dp = [[0] * (max_fleet + 1) for _ in range(max_time + 1)]

    for t in range(1, max_time + 1):
        for w in range(max_fleet + 1):
            dp[t][w] = dp[t - 1][w]

        if t in trades_ending_at:
            for start_time, fleet_cost, profit_val in trades_ending_at[t]:
                for w in range(max_fleet, fleet_cost - 1, -1):
                    dp[t][w] = max(dp[t][w], dp[start_time][w - fleet_cost] + profit_val)
    
    max_profit = 0
    if max_time > 0:
        max_profit = max(dp[max_time])

    print(max_profit)

solve()