oj.uz

Submission #77312

# Submission time Handle Problem Language Result Execution time Memory
77312 2018-09-25T09:45:45 Z MohamedAhmed0 Watching (JOI13_watching) C++14
100 / 100
 281 ms 16564 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 43 ms 15992 KB Output is correct
2 Correct 2 ms 15992 KB Output is correct
3 Correct 43 ms 16032 KB Output is correct
4 Correct 2 ms 16032 KB Output is correct
5 Correct 2 ms 16032 KB Output is correct
6 Correct 2 ms 16032 KB Output is correct
7 Correct 50 ms 16292 KB Output is correct
8 Correct 43 ms 16292 KB Output is correct
9 Correct 44 ms 16292 KB Output is correct
10 Correct 42 ms 16292 KB Output is correct
11 Correct 43 ms 16292 KB Output is correct
12 Correct 42 ms 16292 KB Output is correct
13 Correct 49 ms 16372 KB Output is correct
14 Correct 44 ms 16372 KB Output is correct
15 Correct 43 ms 16372 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16372 KB Output is correct
2 Correct 2 ms 16372 KB Output is correct
3 Correct 2 ms 16372 KB Output is correct
4 Correct 2 ms 16372 KB Output is correct
5 Correct 2 ms 16372 KB Output is correct
6 Correct 2 ms 16372 KB Output is correct
7 Correct 49 ms 16372 KB Output is correct
8 Correct 94 ms 16372 KB Output is correct
9 Correct 211 ms 16432 KB Output is correct
10 Correct 79 ms 16452 KB Output is correct
11 Correct 108 ms 16564 KB Output is correct
12 Correct 281 ms 16564 KB Output is correct
13 Correct 48 ms 16564 KB Output is correct
14 Correct 51 ms 16564 KB Output is correct
15 Correct 51 ms 16564 KB Output is correct