Submission #306081

#	Time	Username	Problem	Language	Result	Execution time	Memory
306081		vipghn2003	Watching (JOI13_watching)	C++14	100 / 100	227 ms	16000 KiB

watching

#include<bits/stdc++.h>

using namespace std;

const int N=2005;
int n,p,q,a[N],dp[N][N];

bool check(int w)
{
    int k1=1,k2=1;
    for(int i=1;i<=n;i++)
    {
        while(a[k1]<a[i]-w+1) k1++;
        while(a[k2]<a[i]-2*w+1) k2++;
        for(int j=0;j<=p;j++)
        {
            dp[i][j]=1e9;
            if(j) dp[i][j]=min(dp[i][j],dp[k1-1][j-1]);
            dp[i][j]=min(dp[i][j],dp[k2-1][j]+1);
        }
    }
    return (dp[n][p]<=q);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>p>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    if(p+q>=n) return cout<<1,0;
    int l=1,r=1e9,res;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(!check(mid)) l=mid+1;
        else
        {
            res=mid;
            r=mid-1;
        }
    }
    cout<<res;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:44:11: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |     cout<<res;
      |           ^~~

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