Submission #1140176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140176		tmm	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	60 / 100	2095 ms	8244 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];
        dp[i] = -1;
    }
    sort(v.begin() + 1, v.end());
}

int main() {
    reading();
    for(int i = 0; i <= n - A; i++) {
        if (dp[i + A] == -1)
            dp[i + A] = max(v[i + A] - v[i + 1], dp[i]);
        else
            dp[i + A] = min(dp[i + A], max(v[i + A] - v[i + 1], dp[i]));
        for (int j = A + 1; j <= B && i + j <= n; j++)
            if(dp[i + j] == -1)
                dp[i + j] = max(v[i + j] - v[i + 1], dp[i]);
            else
                dp[i + j] = min(dp[i + j], max(v[i + j] - v[i + 1], dp[i]));

        cout << i << " " << dp[i] << endl;
    }

    cout << dp[n];

}
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

const int N_max = 1000005;
ifstream fin("a.in");

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];
        dp[i] = -1;
    }
    sort(v.begin() + 1, v.end());
}

int main() {
    reading();
    for(int i = A; i <= n; i++){
        for(int j = A; j <= B && i >= j; j++)
            if(dp[i - j] != -1){
                if(dp[i] == -1)
                    dp[i] = max(dp[i - j], v[i] - v[i - j + 1]);
                else
                    dp[i] = min(dp[i], max(dp[i - j], v[i] - v[i - j + 1]));
            }
    }
    cout << dp[n];

}

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