Submission #1307633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307633		JelaByteEngineer	Watching (JOI13_watching)	C++20	100 / 100	249 ms	16280 KiB

watching

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int CONST=1e9;
bool ok (int mid, int n, int p, int q, vector <ll> &niz)
{
    vector <int> poslm(n), poslv(n);
    for (int i=0; i<n; i++)
    {
        poslm[i]=lower_bound(niz.begin(), niz.end(), niz[i]+mid)-niz.begin();
        poslv[i]=lower_bound(niz.begin(), niz.end(), niz[i]+2*mid)-niz.begin();
    }
    vector <vector <int>> dp(n+1, vector <int> (q+1, CONST));
    dp[0][0]=0;
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<=q; j++)
        {
            if (dp[i][j]==CONST) continue;
            dp[poslm[i]][j]=min(dp[poslm[i]][j], dp[i][j]+1);
            if (j<q) dp[poslv[i]][j+1]=min(dp[poslv[i]][j+1], dp[i][j]);
        }
    }
    for (int i=0; i<=q; i++)
    {
        if (dp[n][i]<=p) return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, p, q;
    cin>>n>>p>>q;
    p=min(n, p); q=min(n, q);
    vector <ll> niz(n);
    for (int i=0; i<n; i++)
    {
        cin>>niz[i];
    }
    sort (niz.begin(), niz.end());
    int ans=CONST;
    int l=1, r=CONST;
    while (l<=r)
    {
        int mid=l+(r-l)/2;
        if (ok(mid, n, p, q, niz))
        {
            r=mid-1;
            ans=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50