#1084097 (C++17) No.974 最後の日までに

• 問題: No.974 最後の日までに
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:19:07
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,716 bytes
• コンパイル時間: 855 ms
• コンパイル使用メモリ: 90,436 KB
• 実行使用メモリ: 232,016 KB
• 最終ジャッジ日時: 2025-05-14 13:19:54
• 合計ジャッジ時間: 7,345 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
sample	-- * 3
other	TLE * 1 -- * 48

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <utility> // For std::move

using namespace std;

// Define long long type for large numbers often needed in competitive programming
typedef long long ll;

/**
 * @brief Updates a map representing states (Favorability -> Max Money).
 * For a given favorability F, ensures that the map stores the maximum possible money M achieved.
 * If F is already a key in the map, it updates the associated money M if the new M is greater.
 * If F is not in the map, it inserts the new pair (F, M).
 * 
 * @param m Reference to the map to be updated.
 * @param F The favorability value.
 * @param M The money value associated with F.
 */
void update_map(map<ll, ll>& m, ll F, ll M) {
    // Find if F already exists as a key in the map
    auto it = m.find(F);
    if (it != m.end()) {
        // If F exists, update the associated money M only if the new M is greater
        it->second = max(it->second, M);
    } else {
        // If F does not exist, insert the new pair (F, M) into the map
        m.insert({F, M});
    }
    // Note: This function implements the "max M per F" filtering strategy.
    // A full Pareto optimality check could be more complex and potentially store more states.
    // Based on problem structure and examples, "max M per F" seems appropriate.
}

int main() {
    // Use faster I/O operations by disabling synchronization with C stdio and unlinking cin/cout.
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int W; // Number of weeks until graduation
    cin >> W;

    // Vectors to store the parameters for each week. Using 1-based indexing for convenience.
    // a[i]: money earned fromアルバイト in week i
    // b[i]: favorability points gained from dating in week i
    // c[i]: money spent for dating in week i
    vector<ll> a(W + 1), b(W + 1), c(W + 1);
    for (int i = 1; i <= W; ++i) {
        cin >> a[i] >> b[i] >> c[i];
    }

    // DP state representation: Use two maps.
    // dp[0]: Stores states (Favorability -> Max Money) achievable at the end of a week, 
    //        such that NO appointment is made for the NEXT week.
    // dp[1]: Stores states (Favorability -> Max Money) achievable at the end of a week,
    //        such that an appointment IS made for the NEXT week.
    map<ll, ll> dp[2]; 
    
    // Base case: At the end of week 0 (which is the start of week 1).
    // Initial favorability F=0, initial money M=0.
    // The problem states she does not have an appointment for week 1.
    // This corresponds to a state in dp[0].
    dp[0][0] = 0; 

    // Iterate through each week from 1 to W
    for (int i = 1; i <= W; ++i) {
        // Temporary maps to store the DP states computed for the end of week i.
        // These will replace dp[0] and dp[1] after processing week i.
        map<ll, ll> next_dp[2];
        
        // Process transitions originating from states that ended week i-1 WITH an appointment FOR week i.
        // These states are currently stored in dp[1].
        // Rule: If she has an appointment for week i, she MUST go on a date.
        if (!dp[1].empty()) { // Check if there are any such states
            for (auto const& [F, M] : dp[1]) { // Iterate through each state (F, M)
                 ll next_F = F + b[i]; // Favorability increases by b[i]
                 ll next_M = M - c[i]; // Money decreases by c[i]
                 // After dating, no appointment is made for the following week (i+1).
                 // Therefore, this resulting state contributes to next_dp[0].
                 update_map(next_dp[0], next_F, next_M);
            }
        }

        // Process transitions originating from states that ended week i-1 with NO appointment FOR week i.
        // These states are currently stored in dp[0].
        // Rule: If she has no appointment, she can choose either 'Go to school' or 'Do アルバイト'.
         if (!dp[0].empty()) { // Check if there are any such states
            for (auto const& [F, M] : dp[0]) { // Iterate through each state (F, M)
                
                // Option 1: Choose 'Go to school'
                if (i < W) { // If it's not the last week
                    // This action makes an appointment for week i+1.
                    // State (F, M) transitions to a state contributing to next_dp[1].
                    update_map(next_dp[1], F, M);
                } else { // If i == W (the last week)
                     // The problem states "if i=W, nothing happens".
                     // This means the state (F, M) remains, and no appointment is relevant after week W.
                     // The resulting state effectively has no appointment for 'next week', contributing to next_dp[0].
                     update_map(next_dp[0], F, M);
                }

                // Option 2: Choose 'Do アルバイト'
                ll next_M = M + a[i]; // Money increases by a[i]. Favorability F remains unchanged.
                // This action does not make an appointment for week i+1.
                // The resulting state (F, next_M) contributes to next_dp[0].
                update_map(next_dp[0], F, next_M);
            }
        }
        
        // After processing all transitions for week i, update the main DP state maps.
        // Using std::move can be more efficient for large maps as it avoids copying.
        dp[0] = move(next_dp[0]);
        dp[1] = move(next_dp[1]);
    }

    // After iterating through all W weeks, the final possible states are in dp[0] and dp[1].
    // We need to find the maximum favorability F among all final states where the money M is non-negative.
    ll max_F = 0; // Initialize maximum Favorability found so far to 0.
                  // The initial state (0, 0) is always reachable and satisfies M >= 0, so 0 is a possible result.

    // Check states in dp[0] (ended week W without an appointment for W+1)
    for (auto const& [F, M] : dp[0]) {
        if (M >= 0) { // Check the final money constraint
            max_F = max(max_F, F); // Update max_F if this state has higher F
        }
    }
     
    // Check states in dp[1] (ended week W having made an appointment for W+1).
    // Based on the rules for week W actions, this map should theoretically be empty.
    // Checking it provides robustness in case of interpretation differences.
    for (auto const& [F, M] : dp[1]) {
         if (M >= 0) { // Check the final money constraint
              max_F = max(max_F, F); // Update max_F if this state has higher F
         }
    }

    // Output the final result: the maximum favorability achievable with non-negative money.
    cout << max_F << endl;

    return 0;
}