oj.uz

Submission #96079

# Submission time Handle Problem Language Result Execution time Memory
96079 2019-02-05T16:26:25 Z Alexa2001 Watching (JOI13_watching) C++17
0 / 100
 97 ms 15976 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2005, inf = 1e9;

int N, P, Q, n;
int A[Nmax], a[Nmax], dp[Nmax][Nmax];

bool check(int W)
{
    int i, j = 1, k = 1, it;

    for(i=1; i<=N; ++i)
    {
        while(W - 1 < A[i] - A[j]) ++j;
        while(2*W - 1 < A[i] - A[k]) ++k;

        for(it=0; it<=i && it<=P; ++it)
            dp[i][it] = min( (it != 0 ? dp[j-1][it-1] : inf), dp[k-1][it] + 1);

        for(; it<=P; ++it) dp[i][it] = inf;
    }
    return (dp[N][P] <= Q);
}

int main()
{
  //  freopen("input", "r", stdin);

    int i;
    cin >> n >> P >> Q;
    for(i=1; i<=n; ++i) cin >> a[i];

    sort(a+1, a+n+1);

    for(i=1; i<=n; ++i)
        if(a[i] != a[i-1]) A[++N] = a[i];

    P = min(P, N); Q = min(Q, N);

    int st = 1, dr = inf, mid;
    while(st <= dr)
    {
        mid = (st+dr)/2;
        if(check(mid)) dr = mid-1;
            else st = mid+1;
    }
    cout << st << '\n';
    return 0;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 2 ms 764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8440 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Incorrect 97 ms 15976 KB Output isn't correct
4 Halted 0 ms 0 KB -