oj.uz

Submission #83686

# Submission time Handle Problem Language Result Execution time Memory
83686 2018-11-09T21:13:29 Z Bodo171 Watching (JOI13_watching) C++14
50 / 100
 227 ms 16932 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<=n;j++)
            dp[i][j]=min(dp[p1-1][j-1],dp[p2-1][j]+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 6 ms 1016 KB Output is correct
2 Correct 2 ms 1016 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 2 ms 1016 KB Output is correct
5 Correct 2 ms 1016 KB Output is correct
6 Correct 2 ms 1016 KB Output is correct
7 Correct 3 ms 1228 KB Output is correct
8 Correct 3 ms 1296 KB Output is correct
9 Correct 3 ms 1296 KB Output is correct
10 Correct 3 ms 1296 KB Output is correct
11 Correct 4 ms 1296 KB Output is correct
12 Correct 3 ms 1296 KB Output is correct
13 Correct 3 ms 1296 KB Output is correct
14 Correct 3 ms 1296 KB Output is correct
15 Correct 3 ms 1296 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 16600 KB Output is correct
2 Correct 2 ms 16600 KB Output is correct
3 Correct 2 ms 16600 KB Output is correct
4 Correct 3 ms 16600 KB Output is correct
5 Correct 3 ms 16600 KB Output is correct
6 Correct 2 ms 16600 KB Output is correct
7 Correct 160 ms 16720 KB Output is correct
8 Correct 182 ms 16784 KB Output is correct
9 Correct 192 ms 16800 KB Output is correct
10 Correct 227 ms 16816 KB Output is correct
11 Correct 166 ms 16832 KB Output is correct
12 Correct 204 ms 16832 KB Output is correct
13 Correct 162 ms 16888 KB Output is correct
14 Correct 163 ms 16912 KB Output is correct
15 Incorrect 186 ms 16932 KB Output isn't correct