#1083774 (C++17) No.1430 Coup de Coupon

• 問題: No.1430 Coup de Coupon
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:00:15
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,540 bytes
• コンパイル時間: 1,105 ms
• コンパイル使用メモリ: 85,696 KB
• 実行使用メモリ: 393,988 KB
• 最終ジャッジ日時: 2025-05-14 13:02:35
• 合計ジャッジ時間: 6,723 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
other	AC * 7 TLE * 1 -- * 19

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // Include for std::accumulate, although manual sum is used here

// Struct to hold information about a potential discount application
// This struct bundles the discount amount with the indices of the item and coupon involved.
struct CouponInfo {
    long long discount; // The amount of discount offered by this coupon on this item
    int item_idx;       // Index of the item (0 to N-1)
    int coupon_idx;     // Index of the coupon (0 to C-1)

    // Custom comparison operator for sorting CouponInfo objects.
    // We want to sort in descending order based on the discount amount.
    // std::sort uses operator< by default. To achieve descending order,
    // we define `a < b` if `a.discount > b.discount`.
    bool operator<(const CouponInfo& other) const {
        // Primary sort key: discount amount (descending order)
        if (discount != other.discount) {
            return discount > other.discount;
        }
        // Secondary sort keys (optional, used for tie-breaking to ensure deterministic behavior)
        // If discounts are equal, sort by item index first, then coupon index (ascending).
        // This tie-breaking doesn't affect the correctness of the final total discount.
        if (item_idx != other.item_idx) {
            return item_idx < other.item_idx;
        }
        return coupon_idx < other.coupon_idx;
    }
};

int main() {
    // Use fast I/O operations to speed up input reading.
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N; // Number of items
    int C; // Number of coupons
    std::cin >> N >> C;

    // Read item prices. Use long long for prices as they can be large ($10^5$)
    // and the total price could exceed the range of a 32-bit integer.
    std::vector<long long> P(N);
    long long total_original_price = 0;
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i];
        total_original_price += P[i]; // Accumulate the total original price of all items.
    }

    // Read coupon details. Each coupon has a type (1 or 2) and a value (X_j).
    // Store them in a vector of pairs.
    std::vector<std::pair<int, int>> coupons(C); 
    for (int j = 0; j < C; ++j) {
        std::cin >> coupons[j].first >> coupons[j].second;
    }

    // Vector to store all potential discount applications (item-coupon pairs).
    std::vector<CouponInfo> potential_discounts;
    
    // Pre-allocate memory for the vector if N*C is potentially large. This can improve performance
    // by avoiding multiple reallocations as elements are added.
    // Cast N to size_t before multiplying with C to prevent potential integer overflow if N*C
    // were large enough to exceed maximum int value (though N, C <= 5000 makes this safe anyway).
    // Check N > 0 and C > 0 because constraints say N, C >= 1.
    if (N > 0 && C > 0) {
       // Using try-catch block is good practice for robust code, but often omitted in competitive programming
       // where constraints usually guarantee valid allocations within limits.
       try {
           potential_discounts.reserve(static_cast<size_t>(N) * C); 
       } catch (const std::bad_alloc& e) {
           // Optional: error handling for memory allocation failure
           // std::cerr << "Memory allocation failed: " << e.what() << std::endl;
           // return 1; // Indicate failure
       }
    }


    // Calculate the discount for every possible pair of item and coupon.
    for (int i = 0; i < N; ++i) { // Iterate through each item
        for (int j = 0; j < C; ++j) { // Iterate through each coupon
            long long current_discount = 0;
            int type = coupons[j].first;
            int value = coupons[j].second;

            if (type == 1) { // Fixed amount discount coupon (T_j = 1)
                // The discount is the minimum of the item's price P_i and the coupon's fixed value X_j.
                // The final price is max(P_i - X_j, 0). The discount amount is P_i - max(P_i - X_j, 0) = min(P_i, X_j).
                // Ensure calculation uses long long to prevent overflow issues.
                current_discount = std::min(static_cast<long long>(value), P[i]);
            } else { // type == 2, Percentage discount coupon (T_j = 2)
                // The discount is calculated as P_i * X_j / 100.
                // The final price is P_i * (100 - X_j) / 100. The discount is P_i - final_price.
                // Since P[i] is guaranteed to be a multiple of 100, this division results in an exact integer.
                // Use long long for intermediate multiplication P[i] * value to prevent potential overflow.
                current_discount = P[i] * static_cast<long long>(value) / 100;
            }
            
            // Add the calculated discount info (discount amount, item index, coupon index)
            // to our list of potential discounts.
            // Since problem constraints state P_i >= 100 and X_j >= 1, all valid discounts will be positive.
            potential_discounts.push_back({current_discount, i, j});
        }
    }

    // Sort the potential discounts. Using the custom comparison operator in CouponInfo struct,
    // this sorts them in descending order based on the discount amount.
    std::sort(potential_discounts.begin(), potential_discounts.end());

    // Flags to track if an item or a coupon has already been used in the final selection.
    // Initialize all to false.
    std::vector<bool> item_used(N, false);
    std::vector<bool> coupon_used(C, false);
    
    long long total_discount = 0; // Accumulator for the total discount achieved. Initialize to 0.
    int coupons_applied = 0;      // Counter for the number of coupons successfully applied. Initialize to 0.
    
    // The maximum number of coupons that can be applied is limited by the number of items (N)
    // and the number of coupons (C). We can apply at most min(N, C) coupons.
    int limit = std::min(N, C);   

    // Greedily select the best discounts.
    // Iterate through the sorted list of potential discounts (from highest discount amount to lowest).
    for (const auto& info : potential_discounts) {
        // If we have already applied the maximum possible number of coupons, we can stop early.
        if (coupons_applied == limit) {
            break;
        }

        int item_idx = info.item_idx;
        int coupon_idx = info.coupon_idx;

        // Check if both the item and the coupon involved in this potential discount application
        // are still available (i.e., have not been used yet).
        if (!item_used[item_idx] && !coupon_used[coupon_idx]) {
            // If both are available, we choose to apply this coupon to this item.
            total_discount += info.discount; // Add the discount amount to the total accumulated discount.
            item_used[item_idx] = true;      // Mark the item as used, so it cannot receive another coupon.
            coupon_used[coupon_idx] = true;  // Mark the coupon as used, so it cannot be applied again.
            coupons_applied++;               // Increment the count of applied coupons.
        }
    }

    // The final minimum cost to buy all items is the total original price minus the maximum total discount achieved.
    long long final_cost = total_original_price - total_discount;
    
    // Output the final minimum cost. Ensure a newline character at the end.
    std::cout << final_cost << std::endl;

    return 0; // Indicate successful execution.
}