oj.uz

Submission #92681

# Submission time Handle Problem Language Result Execution time Memory
92681 2019-01-04T10:03:53 Z LittleFlowers__ Watching (JOI13_watching) C++14
100 / 100
 209 ms 16252 KB 
#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

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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 16248 KB Output is correct
2 Correct 40 ms 16156 KB Output is correct
3 Correct 41 ms 16120 KB Output is correct
4 Correct 38 ms 16120 KB Output is correct
5 Correct 39 ms 16120 KB Output is correct
6 Correct 43 ms 16120 KB Output is correct
7 Correct 43 ms 16120 KB Output is correct
8 Correct 35 ms 16120 KB Output is correct
9 Correct 39 ms 16120 KB Output is correct
10 Correct 35 ms 16240 KB Output is correct
11 Correct 40 ms 16120 KB Output is correct
12 Correct 37 ms 16196 KB Output is correct
13 Correct 38 ms 16248 KB Output is correct
14 Correct 32 ms 16124 KB Output is correct
15 Correct 35 ms 16120 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16248 KB Output is correct
2 Correct 33 ms 16120 KB Output is correct
3 Correct 189 ms 16212 KB Output is correct
4 Correct 159 ms 16248 KB Output is correct
5 Correct 61 ms 16248 KB Output is correct
6 Correct 209 ms 16248 KB Output is correct
7 Correct 44 ms 16120 KB Output is correct
8 Correct 67 ms 16120 KB Output is correct
9 Correct 99 ms 16248 KB Output is correct
10 Correct 169 ms 16248 KB Output is correct
11 Correct 61 ms 16120 KB Output is correct
12 Correct 135 ms 16252 KB Output is correct
13 Correct 49 ms 16188 KB Output is correct
14 Correct 50 ms 16248 KB Output is correct
15 Correct 48 ms 16220 KB Output is correct