#include #include #include #include // 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(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 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 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; }