제출 #1140095

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

plaukimo_varzybos

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;
int times[MAX_N+5];
int N, A, B;

bool isFeasible(int maxDiff) {

    int valid=0;
    for (int aux=A; aux<=B; ++aux)
    {
        int OUT=1;

        int groupStart = 0;  // Indexul de început al grupului curent

        for (int i = 0; i < N && OUT; ++i) {
            // Dacă diferența dintre cel mai lent și cel mai rapid depășește maxDiff sau grupul devine prea mare (> B), încheiem grupul curent
            if (times[i] - times[groupStart] > maxDiff || i - groupStart + 1 > aux) {
                // Verificăm dacă grupul format are o dimensiune validă
                if (i - groupStart < A) OUT=0;
                // Începem un nou grup
                groupStart = i;
            }
        }

        // Verificăm dacă ultimul grup este valid
        if (N - groupStart < A) OUT=0;

        if (OUT==1)
            valid=1;
    }

    if(valid==1)
        return true;
    return false;
}

int main() {

    cin >> N >> A >> B;

    for (int i = 0; i < N; ++i) {
        cin >> times[i];
    }

    //Sort
    sort(times, times + N);

    //Binary search for the minimum maximum difference
    int low = 0;
    int high = times[N - 1] - times[0];
    int result = high;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if this mid value is feasible
        if (isFeasible(mid)) {
            result = mid; // Update result and try for a smaller maximum difference
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << result << "\n";

    return 0;
}

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