Submission #802765

#	Time	Username	Problem	Language	Result	Execution time	Memory
802765		12345678	Watching (JOI13_watching)	C++17	100 / 100	159 ms	15956 KiB

watching

#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+10;
int n, p, q, dp[nx][nx], ans;
vector<int> v;

bool can(int w)
{
    for (int i=0; i<n; i++)
    {
        int ps=(upper_bound(v.begin(), v.end(), v[i]-w)-v.begin())-1;
        int pb=(upper_bound(v.begin(), v.end(), v[i]-2*w)-v.begin())-1;
        for (int j=0; j<=q; j++) dp[i][j]=1e9, dp[i][j]=min((pb==-1||j==0)?(j==0?nx:0):dp[pb][j-1], (ps==-1)?1:dp[ps][j]+1);
    }
    return dp[n-1][q]<=p;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>p>>q;
    v.resize(n);
    for (auto &x:v) cin>>x;
    sort(v.begin(), v.end());
    if (p+q>=n)
    {
        cout<<1;
        return 0;
    }
    int l=1, r=1e9+1000;
    while (l<r)
    {
        int md=(l+r)/2;
        //cout<<md<<'\n';
        if (can(md)) r=md;
        else l=md+1;
    }
    cout<<r;
}

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