제출 #1140180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140180		pmm	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	10 / 100	135 ms	8264 KiB

plaukimo_varzybos

#include <bits/stdc++.h>
using namespace std;

// Verifică dacă putem împărți toți înotătorii în grupe consecutive (după sortare),
// fiecare grupă având mărimea cuprinsă între A și B,
// astfel încât diferența max-min din orice grupă să fie <= M.
bool canPartition(const vector<long long>& t, long long N, long long A, long long B, long long M) {
    // Parcurgem timpii în ordine, grupându-i cât de mare se poate (dar max B înotători) 
    // fără să depășim diferența M.
    long long start = 0;  // index de început pentru grupul curent
    while (start < N) {
        long long end = start;
        // Extindem grupul atâta timp cât:
        // 1) Diferența de timp nu depășește M
        // 2) Nu trecem de limita maximă de B participanți
        while (end + 1 < N && (t[end + 1] - t[start] <= M) && (end - start + 1 < B)) {
            end++;
        }
        // Dimensiunea efectivă a grupului
        long long groupSize = end - start + 1;
        // Dacă e sub A, nu putem face un grup valid cu gap <= M
        if (groupSize < A) {
            return false;
        }
        // Trecem la următorul grup
        start = end + 1;
    }
    // Dacă am reușit să grupăm toți participanții, înseamnă că e posibil
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N, A, B;
    cin >> N >> A >> B;

    vector<long long> t(N);
    for (int i = 0; i < N; i++) {
        cin >> t[i];
    }
    // Sortăm timpii
    sort(t.begin(), t.end());

    // Căutare binară pe intervalul [0, maxTime - minTime]
    long long low = 0;
    long long high = t[N - 1] - t[0];
    long long answer = high;

    while (low <= high) {
        long long mid = (low + high) / 2;
        if (canPartition(t, N, A, B, mid)) {
            // Dacă reușim cu diferența mid, încercăm una și mai mică
            answer = mid;
            high = mid - 1;
        } else {
            // Dacă nu reușim cu mid, trebuie să mărim diferența
            low = mid + 1;
        }
    }

    cout << answer << "\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40