Submission #1140241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140241		12345678	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	100 / 100	782 ms	204444 KiB

plaukimo_varzybos

#include <bits/stdc++.h>

using namespace std;

const int nx=1000005;

int n, a, b, t[nx], dp[nx];
multiset<int> c, mx;
vector<int> addc[nx], remc[nx], addmx[nx], remmx[nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>a>>b;
    for (int i=1; i<=n; i++) cin>>t[i], dp[i]=1e9;
    sort(t+1, t+n+1);
    for (int i=1; i<=n; i++)
    {
        if (dp[i-1]<1e9&&i+a-1<=n)
        {
            if (i+b-1>n) b=n-i+1;
            if (dp[i-1]<=t[i+a-1]-t[i]) addmx[i+a-1].push_back(t[i]), remmx[i+b-1].push_back(t[i]);
            else
            {
                int l=i+a-1, r=i+b-1;
                while (l<r)
                {
                    int md=(l+r+1)/2;
                    if (dp[i-1]>t[md]-t[i]) l=md;
                    else r=md-1;
                }
                addc[i+a-1].push_back(dp[i-1]);
                remc[l].push_back(dp[i-1]);
                if (l<i+b-1) addmx[l+1].push_back(t[i]), remmx[i+b-1].push_back(t[i]);
            }
        }
        for (auto x:addc[i]) c.insert(x);
        for (auto x:addmx[i]) mx.insert(x);
        if (!c.empty()) dp[i]=*c.begin();
        if (!mx.empty()) dp[i]=min(dp[i], t[i]-*prev(mx.end()));
        for (auto x:remc[i]) c.erase(c.find(x));
        for (auto x:remmx[i]) mx.erase(mx.find(x));
    }
    cout<<dp[n];
}

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