結果

問題 No.2329 Nafmo、イカサマをする
ユーザー qwewe
提出日時 2025-05-14 12:58:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,721 bytes
コンパイル時間 622 ms
コンパイル使用メモリ 85,268 KB
実行使用メモリ 93,220 KB
最終ジャッジ日時 2025-05-14 13:00:07
合計ジャッジ時間 5,442 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37 TLE * 2 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// Use long long for scores as they can potentially become large.
// A_i can be up to 10^9, K up to 6. Max score can be up to 6 * 10^9.
using Score = long long;

int main() {
    // Use faster I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N;        // Number of cards
    Score M;      // Maximum allowed score
    int K;        // Maximum number of draws allowed
    std::cin >> N >> M >> K;
    
    // Use a set to store distinct card values. This automatically handles duplicates.
    // We only care about distinct values Nafmo can choose from.
    // Also, only values <= M are relevant. If a card value is > M, choosing it
    // would immediately make the score > M (assuming scores are non-negative),
    // so Nafmo would never choose such a card if aiming for a score <= M.
    // We assume card values A_i are non-negative based on problem context/examples.
    std::set<Score> unique_A_le_M; 
    
    for (int i = 0; i < N; ++i) {
        Score card_value;
        std::cin >> card_value;
        // Only consider card values that are non-negative and less than or equal to M.
        if (card_value >= 0 && card_value <= M) {
             unique_A_le_M.insert(card_value);
        }
    }

    // The dynamic programming approach will compute sets of achievable scores.
    // `current_scores` will hold the set of scores achievable after exactly k-1 draws.
    // It starts with score 0 after 0 draws.
    std::set<Score> current_scores;
    current_scores.insert(0); 
    
    // `all_possible_scores` tracks all unique scores achievable within K draws that are <= M.
    // Initialize with 0, which is always achievable by drawing 0 cards.
    std::set<Score> all_possible_scores;
    all_possible_scores.insert(0); 

    // Iterate from 1 to K draws
    for (int k = 1; k <= K; ++k) {
        // `next_scores` will store scores achievable after exactly k draws.
        std::set<Score> next_scores;
        
        // Optimization: If `current_scores` is empty, it means no score <= M was reachable
        // in the previous step (k-1 draws). Therefore, no scores <= M can be generated
        // in this step (k draws) or subsequent steps. We can break the loop early.
        if (current_scores.empty()) {
            break;
        }

        // Explore states reachable from scores achieved in k-1 draws
        // For each score 's' achievable in k-1 draws:
        for (Score s : current_scores) {
            // Try adding each distinct available card value 'val' (where val <= M)
            for (Score val : unique_A_le_M) {
                // Calculate the potential next score
                Score next_s = s + val;
                
                // Check if the potential score `next_s` does not exceed the maximum allowed score M
                if (next_s <= M) {
                    // Add `next_s` to the set of scores achievable in exactly k draws.
                    // `std::set` automatically handles duplicates: if `next_s` is already present, insert does nothing.
                    next_scores.insert(next_s);
                    
                    // Also, record `next_s` in the set of all possible scores found so far (across all k' <= k draws).
                    // This set will contain scores from all step counts 0 up to the current k.
                    all_possible_scores.insert(next_s);
                }
            }
        }
        
        // Prepare for the next iteration (k+1 draws):
        // The scores computed for step k (`next_scores`) become the basis (`current_scores`) for step k+1.
        // `std::move` is used for potential performance optimization, especially if sets become large.
        // It efficiently transfers ownership of the set's contents without copying.
        current_scores = std::move(next_scores); 
    }

    // After the loop finishes (either completing K steps or breaking early),
    // `all_possible_scores` contains all unique scores <= M achievable by drawing at most K cards.
    // We need the maximum among these scores.
    Score max_score = 0; // Default score is 0, achievable by drawing 0 cards.
    
    // Check if `all_possible_scores` is non-empty. It should contain at least 0 if M >= 0.
    if (!all_possible_scores.empty()) {
        // `rbegin()` returns a reverse iterator pointing to the largest element in the `std::set` (which is sorted).
        // Dereferencing it gives the maximum value.
        max_score = *all_possible_scores.rbegin(); 
    }
    
    // Output the maximum achievable score <= M.
    std::cout << max_score << std::endl;
    
    return 0;
}
0