제출 #1139810

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

plaukimo_varzybos

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N_max = 1000005;
int n, A, B;
vector<int> v;
int dp[N_max];
void reading(){
    cin >> n >> A >> B;
    v.resize(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    sort(v.begin() + 1, v.end());
}

int main() {
    reading();
    for(int i = 1; i < A; i++)
        dp[i] = -1;

    for(int i = A; i <= n; i++){
        if(i < min(2 * A, B)){
            dp[i] = v[i] - v[1];
            continue;
        }
        int L = max(A ,i - B), R = i - A, sol = L;
        while(L <= R){
            int M = (L + R) / 2;
            if(dp[M] - v[i] + v[M + 1] <= 0){
                sol = M;
                L = M + 1;
            }else{
                R = M - 1;
            }
        }
        dp[i] = v[n] - v[1];
        if(i <= B)dp[i] = v[i] - v[1];
        dp[i] = min(dp[i], max(dp[sol], v[i] - v[sol + 1]));
        if(sol != i - A)
            dp[i] = min(dp[i], max(dp[sol + 1],v[i] - v[sol + 2]));
    }
    cout << dp[n];

}

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