oj.uz

Submission #77311

# Submission time Handle Problem Language Result Execution time Memory
77311 2018-09-25T09:43:54 Z MohamedAhmed0 Watching (JOI13_watching) C++14
0 / 100
 17 ms 16244 KB 
#include <bits/stdc++.h>

using namespace std;

int arr[2001] , dp[2001][2001] , x , n;

int solve(int idx , int r , int covered)
{    if(idx == n)
        return 0 ;
    int &ret = dp[idx][r] ;
    if(covered > arr[idx])
        return solve(idx+1 , r , covered);
    if(ret != -1)
        return ret ;
    if(r >= n-idx)
        return 0 ;
    ret = solve(idx+1 , r , arr[idx] + x * 2) + 1 ;
    if(r > 0)
        ret = min(ret , solve(idx+1 , r-1 , arr[idx] + x));
    return ret ;
}
int main()
{
    int p , q;
    cin>>n>>p>>q ;
    if(p+q >= n)
        return cout<<1 , 0 ;
    for(int i = 0 ; i < n ; ++i)
        cin>>arr[i] ;
    sort(arr , arr + n);
    int l = 1 , r = 1e9 , ans = 1e9 ;
    memset(dp  ,-1 , sizeof(dp));
    x = 3 ;
    cout<<solve(0 , p , -1)<<"\n";
    return 0 ;
    while(l <= r)
    {
        memset(dp , -1 , sizeof(dp));
        int mid = (l + r) >> 1 ;
        x = mid ;
        if(solve(0 , p , -1) <= q)
            r = mid-1 , ans = min(ans , mid);
        else
            l = mid+1;
    }
    return cout<<ans , 0 ;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 15992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 16244 KB Output isn't correct
2 Halted 0 ms 0 KB -