概要

本問題は、複数の独立な機械を用いて、制限時間 \(K\) の中で得られる利益を最大化する問題です。各機械は互いに影響を与えず独立して動作するため、「1台の機械が \(K\) 分以内で得られる最大利益」を求め、それを \(M\) 倍することで全体の最大利益を求めることができます。1台の機械の利益最大化は、個数制限なしナップサック問題（完全ナップサック問題）として解くことができます。

考察

1. 機械の独立性

\(M\) 台の機械はそれぞれ独立に動作します。ある機械で製品を製造することが、他の機械の製造に影響を与えることはありません。したがって、問題を以下のように分解できます。 1. 1台の機械が \(K\) 分以内で得られる最大利益 \(X\) を動的計画法（DP）で求める。 2. 全体の最大利益は \(X \times M\) となる。

\(M \le 10^9\) と非常に大きいため、機械1台ずつ個別にシミュレーションを行うと実行時間制限に間に合いませんが、この独立性を利用することで計算量を大幅に削減できます。

2. 1台の機械の利益最大化（個数制限なしナップサック問題）

1台の機械に着目すると、各製品 \(i\) について以下の情報が整理できます。 - 製造にかかる時間：\(T_i\) （ナップサックの「重さ」に相当） - 製造によって得られる純利益：\(P_i - C_i\) （ナップサックの「価値」に相当）

各製品は個数の制限なく何個でも製造できるため、これは「容量 \(K\) のナップサックに、重さ \(T_i\)、価値 \(P_i - C_i\) の品物を個数制限なしで詰め込んで価値を最大化する」という個数制限なしナップサック問題そのものです。

なお、利益が \(0\) 以下の製品（\(P_i - C_i \le 0\)）や、製造時間が稼働時間を超える製品（\(T_i > K\)）は、製造するメリットがないため、あらかじめ考慮から外して構いません。

アルゴリズム

動的計画法（DP）を用いて、1台の機械で得られる最大利益を求めます。

DPテーブルの定義

• \(dp[w]\) ：稼働時間 \(w\) 分以内で得られる最大利益（初期値はすべて \(0\)）

DPの遷移

各製品 \(i\)（利益 \(profit = P_i - C_i > 0\)）について、時間 \(w\) を \(T_i\) から \(K\) まで昇順に走査し、DPテーブルを更新します。

\[dp[w] = \max(dp[w], dp[w - T_i] + profit)\]

※「個数制限なし」であるため、同じ製品を何度も選べるようにループを昇順で行います（「高々1個」の場合は降順にする必要があります）。

最終的な計算

DPテーブルの最大値 \(X = \max_{0 \le w \le K} dp[w]\) を求めます。 求める答えは \(X \times M\) となります。

計算量

• 時間計算量: \(O(N \times K)\) 製品の種類数 \(N\) に対し、それぞれ最大 \(K\) 回の遷移を行います。 制約は \(N \le 500\)、\(K \le 200{,}000\) であるため、最悪でも計算回数は \(500 \times 200{,}000 = 10^8\) 回程度となり、実行時間制限に十分間に合います。

• 空間計算量: \(O(K)\) DPテーブルのサイズは \(K + 1\) です。\(K \le 200{,}000\) なので、メモリ使用量は数メガバイト程度に抑えられ、空間複雑度も非常に小さく安全です。

実装のポイント

• オーバーフローの防止: 答えは最大で \(2^{63}-1\)（64ビット符号付き整数の最大値）以下になることが保証されています。しかし、1台あたりの最大利益 \(X\) と機械の台数 \(M\) の掛け算 \(X \times M\) を行う際、通常の 64 ビット整数型（long long）のまま計算すると、演算の過程でオーバーフローが発生する可能性があります。 C++では、環境依存ですが __int128（または unsigned __int128）を使用することで、128ビット精度で安全に掛け算を行うことができます。計算した後に long long にキャストして出力します。

• 不要な遷移のスキップ: 利益が \(0\) 以下の製品や、1つ作るだけで制限時間を超えてしまう製品（\(T_i > K\)）は、ループの前に continue でスキップすることで無駄な計算を省き、定数倍の高速化を図っています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long M;
    int K;
    if (!(cin >> N >> M >> K)) return 0;

    // dp[w] stores the maximum profit possible using exactly or at most w minutes.
    vector<long long> dp(K + 1, 0);

    for (int i = 0; i < N; ++i) {
        long long C, T, P;
        cin >> C >> T >> P;
        long long profit = P - C;
        
        // If the product is not profitable or takes more time than available, skip it.
        if (profit <= 0 || T > K) {
            continue;
        }
        
        int t = T;
        for (int w = t; w <= K; ++w) {
            if (dp[w - t] + profit > dp[w]) {
                dp[w] = dp[w - t] + profit;
            }
        }
    }

    // Find the maximum profit achievable within K minutes
    long long max_profit_per_machine = 0;
    for (int w = 0; w <= K; ++w) {
        max_profit_per_machine = max(max_profit_per_machine, dp[w]);
    }

    // Calculate the total profit for M machines.
    // Since the answer is guaranteed to fit in a 64-bit signed integer, 
    // we can safely cast the result to long long.
    unsigned __int128 total_profit = (unsigned __int128)max_profit_per_machine * M;
    long long ans = (long long)total_profit;

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。