Submission #765258

#	Time	Username	Problem	Language	Result	Execution time	Memory
765258		IsaL	Watching (JOI13_watching)	C++17	100 / 100	296 ms	32784 KiB

watching

#include<bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long, long long>

int tc;
long long n,p,q,arr[2069],range_kecil[2069],range_besar[2069],dp[2069][2069];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long i,j;
    cin>>n>>p>>q;
    for(i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    sort(arr+1,arr+n+1);
    long long l = 1, r = 1e10,mid, ans = 1;
    for(mid=(l+r)/2ll;l<=r;mid=(l+r)/2ll)
    {
        int besar = 0, kecil = 0;
        for(i=1;i<=n;i++)
        {
            while(arr[i]-arr[besar+1] >= 2 * mid)
            {
                besar++;
            }
            while(arr[i]-arr[kecil+1] >= mid)
            {  
                kecil++;
            }
            range_besar[i] = besar;
            range_kecil[i] = kecil;
        }
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=min(n,p);j++)
            {
                dp[i][j] = 1e18 * (i > 0ll);
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=0;j<=min(n,p);j++)
            {
                dp[i][j] = dp[range_besar[i]][j]+1;
                if(j) 
                {
                    dp[i][j] = min(dp[i][j], dp[range_kecil[i]][j-1]);
                }
            }
        }
        // cout<<mid<<" : "<<dp[n][min(n,p)]<<'\n';
        if(dp[n][min(n,p)] <= q)
        {
            ans = mid;
            r = mid-1;
        }
        else
        {
            l = mid+1;
        }
    }
    cout<<ans<<'\n';
}

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