oj.uz

Submission #51459

# Submission time Handle Problem Language Result Execution time Memory
51459 2018-06-18T03:16:00 Z vivukhue Watching (JOI13_watching) C++14
100 / 100
 126 ms 16380 KB 
#include <bits/stdc++.h>
#define fw(i,l,r) for (int i=l;i<r;i++)

using namespace std;
int n,p,q;
int a[2001];
int fars[2001];
int farl[2001];
int dp[2001][2001];

bool check(int w)
{
    for(int i=0;i<n;i++)
    {
        fars[i] = upper_bound(a,a+n,a[i]+w-1) - a;
        farl[i] = upper_bound(a,a+n,a[i]+2*w-1) - a;
    }
    memset(dp,-1,sizeof(dp));
    dp[0][0] = 0;
    for(int i=0;i<=p;i++)
    {
        for(int j=0;j<=q;j++)
        {
            if(dp[i][j]!=-1)
            {
                if(dp[i][j]==n)
                    return true;
                dp[i+1][j] = max(dp[i+1][j],fars[dp[i][j]]);
                dp[i][j+1] = max(dp[i][j+1],farl[dp[i][j]]);
            }
        }
    }

    return false;
}

signed main()
{
    cin>>n>>p>>q;
    for(int i=0;i<n;i++)
        cin>>a[i];

    if(p+q>=n)
    {
        cout<<1;
        return 0;
    }

    sort(a,a+n);
    //for(int i=0;i<n;i++)
        //cout<<a[i]<<" ";

    int L=1,R=1e9;
    while(L!=R)
    {
        int mid = (L+R)/2;
        if(check(mid))
            R = mid;
        else
            L = mid+1;
    }

    cout<<L;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 15992 KB Output is correct
2 Correct 3 ms 15992 KB Output is correct
3 Correct 51 ms 16216 KB Output is correct
4 Correct 2 ms 16216 KB Output is correct
5 Correct 2 ms 16216 KB Output is correct
6 Correct 2 ms 16216 KB Output is correct
7 Correct 46 ms 16216 KB Output is correct
8 Correct 43 ms 16216 KB Output is correct
9 Correct 40 ms 16244 KB Output is correct
10 Correct 50 ms 16244 KB Output is correct
11 Correct 54 ms 16244 KB Output is correct
12 Correct 42 ms 16244 KB Output is correct
13 Correct 82 ms 16256 KB Output is correct
14 Correct 54 ms 16256 KB Output is correct
15 Correct 47 ms 16256 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16256 KB Output is correct
2 Correct 2 ms 16256 KB Output is correct
3 Correct 3 ms 16256 KB Output is correct
4 Correct 3 ms 16256 KB Output is correct
5 Correct 3 ms 16256 KB Output is correct
6 Correct 4 ms 16256 KB Output is correct
7 Correct 48 ms 16256 KB Output is correct
8 Correct 76 ms 16380 KB Output is correct
9 Correct 63 ms 16380 KB Output is correct
10 Correct 115 ms 16380 KB Output is correct
11 Correct 53 ms 16380 KB Output is correct
12 Correct 126 ms 16380 KB Output is correct
13 Correct 48 ms 16380 KB Output is correct
14 Correct 50 ms 16380 KB Output is correct
15 Correct 52 ms 16380 KB Output is correct