oj.uz

Submission #92674

# Submission time Handle Problem Language Result Execution time Memory
92674 2019-01-04T09:52:47 Z LittleFlowers__ Watching (JOI13_watching) C++14
50 / 100
 1000 ms 32068 KB 
#include <bits/stdc++.h>
#define int long long
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define reset(f, x) memset(f, x, sizeof(f))
using namespace std;
const int N=2010;
int n,p,q;
int a[N];
int f[N][N];
bool C(int x)
{
    reset(f,-1);
    f[0][p]=q;
    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;
            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;
            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()
{
    //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=1e9,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

watching.cpp:30:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 31980 KB Output is correct
2 Correct 263 ms 31980 KB Output is correct
3 Correct 234 ms 31864 KB Output is correct
4 Correct 268 ms 31992 KB Output is correct
5 Correct 165 ms 31996 KB Output is correct
6 Correct 260 ms 31980 KB Output is correct
7 Correct 272 ms 32068 KB Output is correct
8 Correct 242 ms 31992 KB Output is correct
9 Correct 276 ms 31988 KB Output is correct
10 Correct 255 ms 31992 KB Output is correct
11 Correct 268 ms 31944 KB Output is correct
12 Correct 277 ms 31992 KB Output is correct
13 Correct 257 ms 31988 KB Output is correct
14 Correct 265 ms 31992 KB Output is correct
15 Correct 262 ms 31864 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 32008 KB Output is correct
2 Correct 264 ms 31864 KB Output is correct
3 Execution timed out 1044 ms 31996 KB Time limit exceeded
4 Halted 0 ms 0 KB -