結果

問題 No.1248 Kth Sum
ユーザー qwewe
提出日時 2025-05-14 13:19:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,701 bytes
コンパイル時間 776 ms
コンパイル使用メモリ 78,488 KB
実行使用メモリ 14,208 KB
最終ジャッジ日時 2025-05-14 13:20:42
合計ジャッジ時間 3,973 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <numeric> // This header is included but not directly used in the final code logic.

// Use type alias 'll' for long long integers to handle potentially large sums.
// A_i can be up to 10^9. The sum of N such elements can exceed the capacity of a 32-bit integer.
using ll = long long;

int main() {
    // Optimize standard C++ streams for faster I/O operations.
    // This is common practice in competitive programming to avoid Time Limit Exceeded verdicts.
    std::ios_base::sync_with_stdio(false); // Untie C++ standard streams from C standard streams.
    std::cin.tie(NULL); // Untie cin from cout.

    int N; // Number of elements in the sequence A. N <= 2 * 10^5.
    int K_int; // Minimum length of each subsequence. K <= N.
    
    // Read N and K from standard input.
    std::cin >> N >> K_int;
    
    // Convert K to size_t for safe comparison with multiset::size().
    // size_t is an unsigned integer type typically used for sizes and counts.
    // Using size_t avoids potential issues with signed/unsigned integer comparisons.
    size_t K = static_cast<size_t>(K_int); 

    // Declare a vector 'A' of size N to store the sequence elements.
    // Use long long type for elements as they can be up to 10^9.
    std::vector<ll> A(N);
    // Read N elements into the vector A.
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
    }
    
    // Use a multiset data structure named 'candidate'.
    // A multiset stores elements in sorted order and allows duplicate values.
    // It will be used to dynamically maintain a collection of elements.
    std::multiset<ll> candidate;
    
    // Variable to keep track of the sum of elements currently present in the 'candidate' multiset.
    // Initialize sum to 0. Use long long to prevent overflow.
    ll current_sum = 0; 
    
    // Iterate through each element of the input sequence A.
    for (int i = 0; i < N; ++i) {
        // Insert the current element A[i] into the 'candidate' multiset.
        // The multiset automatically maintains sorted order.
        candidate.insert(A[i]);
        // Add the value of the inserted element to the running sum.
        current_sum += A[i];
        
        // Check if the number of elements in the 'candidate' multiset has exceeded K.
        if (candidate.size() > K) {
            // If the size is greater than K, it means we need to remove an element.
            // The algorithm logic requires removing the largest element currently in the set.
            
            // Find an iterator pointing to the largest element in the multiset.
            // `candidate.end()` points one position past the last element.
            auto it_largest = candidate.end();
            // Decrement the iterator to make it point to the actual largest (last) element.
            --it_largest; 
            // Dereference the iterator to get the value of the largest element.
            ll largest_val = *it_largest; 
            
            // Remove the largest element from the multiset using the iterator.
            candidate.erase(it_largest);
            // Subtract the value of the removed element from the running sum.
            current_sum -= largest_val;
        }
    }
    
    // After processing all N elements, the `current_sum` holds the sum of elements
    // remaining in the `candidate` multiset. This sum is the minimum possible sum
    // of the K-th elements according to the algorithm's logic.
    // Print the final minimum sum to standard output, followed by a newline.
    std::cout << current_sum << std::endl;
    
    // Return 0 to indicate successful execution.
    return 0;
}
0