oj.uz

Submission #77293

# Submission time Handle Problem Language Result Execution time Memory
77293 2018-09-24T19:40:15 Z MohamedAhmed0 Watching (JOI13_watching) C++14
0 / 100
 169 ms 31980 KB 
#include <bits/stdc++.h>

using namespace std;

long long dp[2001][2001] , arr[2001];

long long n , p , q ;

long long check(long long idx , long long r , long long re , long long x , long long covered)
{
    if(idx == n)
       return 1 ;
    long long &ret = dp[idx][r] ;
    if(ret != -1)
        return ret ;
    if(r + re >= n-1 - idx + (arr[idx] > covered))
        return ret = 1 ;
    ret = 0 ;
    if(arr[idx] <= covered)
        ret = check(idx+1 , r , re , x , covered);
    else
    {
        if(r == 0 && re == 0)
            return 0 ;
        if(r != 0)
          ret = check(idx+1 , r-1 , re , x , arr[idx] + x-1);
        if(re != 0)
          ret = max(ret , check(idx+1 , r , re-1 , x , arr[idx] + x*2-1));
    }
    return ret ;
}

int main()
{
    cin>>n>>p>>q ;
    if(p+q >= n)
        return cout<<1 , 0 ;
    long long MAX = 0 ;
    for(long long i = 0 ; i < n ; ++i)
    {
         cin>>arr[i] ;
         MAX = max(MAX , arr[i]);
    }
    //sort(arr , arr + n + 1);
    sort(arr , arr + n);
    long long l = 1 , r = MAX , ans = 1e9;
    while(l <= r)
    {
        memset(dp , -1 , sizeof(dp));
        long long mid = (l + r) / 2 ;
        if(check(0 , p , q , mid , 0))
            r = mid-1 , ans = min(ans , mid);
        else
            l = mid+1;
    }
    return cout<<ans<<"\n" , 0 ;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 31708 KB Output is correct
2 Correct 2 ms 31708 KB Output is correct
3 Correct 169 ms 31800 KB Output is correct
4 Correct 2 ms 31800 KB Output is correct
5 Correct 2 ms 31800 KB Output is correct
6 Correct 3 ms 31800 KB Output is correct
7 Incorrect 156 ms 31912 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 31936 KB Output is correct
2 Correct 2 ms 31936 KB Output is correct
3 Correct 2 ms 31936 KB Output is correct
4 Correct 2 ms 31936 KB Output is correct
5 Correct 2 ms 31936 KB Output is correct
6 Correct 2 ms 31936 KB Output is correct
7 Incorrect 150 ms 31980 KB Output isn't correct
8 Halted 0 ms 0 KB -