제출 #1189241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189241		Zakir060	Stove (JOI18_stove)	C++20	100 / 100	12 ms	1864 KiB

stove

#include <iostream>
#include <vector>
#include <algorithm> // sort üçün
#include <numeric>   // accumulate üçün (alternativ)

int main() {
    // Giriş/çıxışı sürətləndirmək üçün (böyük N üçün vacib ola bilər)
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    long long k; // K də N qədər böyük ola bilər
    std::cin >> n >> k;

    // Əgər hər qonaq üçün kifayət qədər kibritimiz varsa
    if (k >= n) {
        std::cout << n << std::endl;
        return 0;
    }

    // Qonaqların gəliş vaxtları (böyük ola bilər)
    std::vector<long long> t(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> t[i];
    }

    // Qonaqlar arasındakı boşluqların uzunluqları
    std::vector<long long> gaps;
    // N-1 boşluq olacağı üçün yer ayırmaq performansı artıra bilər
    gaps.reserve(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        // Növbəti qonağın gəlişi - Hazırkı qonağın gedişi
        long long gap_length = t[i + 1] - (t[i] + 1);
        // Məsələnin şərtinə görə Ti < Ti+1, yəni T[i+1] >= T[i] + 1,
        // buna görə gap_length həmişə >= 0 olmalıdır.
        gaps.push_back(gap_length);
    }

    // Boşluqları artan sırada çeşidləyirik ki, ən kiçikləri seçə bilək
    std::sort(gaps.begin(), gaps.end());

    // Başlanğıc minimal işləmə müddəti (hər qonaq üçün 1 vahid)
    long long total_time = n;

    // Birləşdirməli olduğumuz (kibritə qənaət etmək üçün) boşluqların sayı
    long long num_gaps_to_bridge = n - k;

    // Ən kiçik 'num_gaps_to_bridge' sayda boşluğun uzunluğunu ümumi vaxta əlavə edirik
    for (long long i = 0; i < num_gaps_to_bridge; ++i) {
        // Əmin olmaq üçün ki, kifayət qədər boşluq var (n > k və n > 1 şərti ilə həmişə doğrudur)
        if (i < gaps.size()) {
            total_time += gaps[i];
        } else {
             // Bu hal n=1 və k<n (mümkün deyil) və ya n>1, k<n hallarında baş verməməlidir.
            break;
        }
    }

    /* Alternativ olaraq std::accumulate ilə:
    if (num_gaps_to_bridge > 0 && !gaps.empty()) {
        // C++11 və sonrası: Başlanğıc dəyər üçün 0LL istifadə edərək long long toplamanı təmin edin
        total_time += std::accumulate(gaps.begin(),
                                      gaps.begin() + std::min((long long)gaps.size(), num_gaps_to_bridge),
                                      0LL);
    }
    */

    std::cout << total_time << std::endl;

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50