Submission #92681

#	Time	Username	Problem	Language	Result	Execution time	Memory
92681		LittleFlowers__	Watching (JOI13_watching)	C++14	100 / 100	209 ms	16252 KiB

watching

#include <bits/stdc++.h>
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define reset(f, x) memset(f, x, sizeof(f))
#define max(a,b) (a>b?a:b)
using namespace std;
const int N=2010;
int n,p,q;
int a[N],l[N],r[N];
int f[N][N];
bool C(int x)
{
    reset(f,-1);
    f[0][p]=q;
    forinc(i,0,n-1) l[i]=upper_bound(a+1,a+n+1,a[i+1]+x-1)-a-1,
                    r[i]=upper_bound(a+1,a+n+1,a[i+1]+x*2-1)-a-1;
    forinc(i,0,n-1) forinc(j,0,p) if(f[i][j]>-1)
    {
        if(j)
        {
            //int t=upper_bound(a+1,a+n+1,a[i+1]+x-1)-a-1;
            int t=l[i];
            f[t][j-1]=max(f[t][j-1],f[i][j]);
        }
        if(f[i][j])
        {
            //int t=upper_bound(a+1,a+n+1,a[i+1]+x*2-1)-a-1;
            int t=r[i];
            f[t][j]=max(f[t][j],f[i][j]-1);
        }
    }
    forinc(i,0,p) if(f[n][i]>-1) return 1;
    return 0;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("WATCHING.inp","r",stdin);
    cin>>n>>p>>q;p=min(p,n),q=min(q,n);
    for(int i=1; i<=n; ++i) cin>>a[i];
    sort(a+1,a+n+1);
    int l=1,m,r=a[n],ans;
    while(l<=r)
    {
        m=l+(r-l)/2;
        if(C(m)) ans=m,r=m-1;
        else l=m+1;
    }
    cout<<ans;
}

Compilation message (stderr)

watching.cpp:34:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
watching.cpp: In function 'int main()':
watching.cpp:49:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<ans;
     ~~~~^~~~~

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