oj.uz

Submission #83688

# Submission time Handle Problem Language Result Execution time Memory
83688 2018-11-09T21:18:02 Z Bodo171 Watching (JOI13_watching) C++14
50 / 100
 217 ms 16356 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=2005;
int dp[nmax][nmax];
int v[nmax];
int n,p,q,i,j,p1,p2,val;
bool check(int val)
{
    for(i=1;i<=n;i++)
        for(j=0;j<=p;j++)
           dp[i][j]=q+1;
    p1=p2=1;
    for(i=1;i<=n;i++)
    {
        while(v[i]-v[p1]+1>val)
            p1++;
        while(v[i]-v[p2]+1>2*val)
            p2++;
        for(j=1;j<=p;j++)
            dp[i][j]=min(dp[p1-1][j-1],dp[p2-1][j]+1);
        dp[0][j]=dp[p2-1][0]+1;
    }
    for(i=0;i<=p;i++)
        if(dp[n][i]<=q)
          return 1;
    return 0;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>p>>q;
    for(i=1;i<=n;i++)
        cin>>v[i];
    sort(v+1,v+n+1);
    if(p+q>=n)
    {
        cout<<"1";
        return 0;
    }
    val=(1<<29)-1;
    for(int p=28;p>=0;p--)
        if(check(val-(1<<p)))
           val-=(1<<p);
    cout<<val;
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 4 ms 760 KB Output is correct
7 Correct 2 ms 944 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 2 ms 944 KB Output is correct
10 Correct 2 ms 944 KB Output is correct
11 Correct 3 ms 944 KB Output is correct
12 Correct 3 ms 944 KB Output is correct
13 Correct 2 ms 948 KB Output is correct
14 Correct 2 ms 948 KB Output is correct
15 Correct 3 ms 948 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8496 KB Output is correct
2 Correct 2 ms 8496 KB Output is correct
3 Correct 2 ms 8496 KB Output is correct
4 Correct 3 ms 8496 KB Output is correct
5 Correct 2 ms 8496 KB Output is correct
6 Correct 2 ms 8496 KB Output is correct
7 Correct 11 ms 8632 KB Output is correct
8 Correct 27 ms 9648 KB Output is correct
9 Correct 130 ms 14568 KB Output is correct
10 Correct 217 ms 16356 KB Output is correct
11 Correct 21 ms 16356 KB Output is correct
12 Correct 122 ms 16356 KB Output is correct
13 Correct 11 ms 16356 KB Output is correct
14 Correct 14 ms 16356 KB Output is correct
15 Incorrect 12 ms 16356 KB Output isn't correct