oj.uz

Submission #114315

# Submission time Handle Problem Language Result Execution time Memory
114315 2019-05-31T20:48:32 Z MohamedAhmed04 Watching (JOI13_watching) C++14
100 / 100
 234 ms 16164 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 ;
    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
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16000 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 44 ms 16092 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 37 ms 16000 KB Output is correct
8 Correct 40 ms 16000 KB Output is correct
9 Correct 40 ms 16080 KB Output is correct
10 Correct 39 ms 16000 KB Output is correct
11 Correct 42 ms 15992 KB Output is correct
12 Correct 38 ms 16000 KB Output is correct
13 Correct 39 ms 16000 KB Output is correct
14 Correct 39 ms 16000 KB Output is correct
15 Correct 38 ms 16000 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16056 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 47 ms 16000 KB Output is correct
8 Correct 82 ms 16064 KB Output is correct
9 Correct 184 ms 16120 KB Output is correct
10 Correct 84 ms 16164 KB Output is correct
11 Correct 81 ms 16120 KB Output is correct
12 Correct 234 ms 16120 KB Output is correct
13 Correct 40 ms 16000 KB Output is correct
14 Correct 42 ms 16000 KB Output is correct
15 Correct 42 ms 16000 KB Output is correct