Submission #96080

#	Time	Username	Problem	Language	Result	Execution time	Memory
96080		Alexa2001	Watching (JOI13_watching)	C++17	100 / 100	114 ms	16120 KiB

watching

#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] = 0;
    }
    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: 50 / 50
• Subtask 2: 50 / 50