Submission #96073

#	Time	Username	Problem	Language	Result	Execution time	Memory
96073		Alexa2001	Watching (JOI13_watching)	C++17	0 / 100	2 ms	376 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(A[j] + W - 1 < A[i]) ++j;
        while(A[k] + 2*W - 1 < A[i]) ++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 = 0, dr = N, mid;
    while(st <= dr)
    {
        mid = (st+dr)/2;
        if(check(mid)) dr = mid-1;
            else st = mid+1;
    }
    cout << st << '\n';
    return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50