Submission #366312

#	Time	Username	Problem	Language	Result	Execution time	Memory
366312		idk321	Watching (JOI13_watching)	C++11	100 / 100	314 ms	16236 KiB

watching

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2005;
int dp[N][N];
int n,p, q;
int a[N];

bool poss(ll w)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++) dp[i][j] = 0;
    }

    int next[N][2];
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int first = a[j];
            int add = w - 1;
            if (i == 1) add += w;
            auto it = upper_bound(a, a + n, first + add);
            it--;
            next[j][i] = it - a + 1;
        }
    }
    for (int i = p; i >= 0; i--)
    {
        for (int j = q; j >= 0; j--)
        {

            if (dp[i][j] == n)
            {
                dp[0][0] = n;
            } else
            {
                if (i != 0)
                {
                    dp[i - 1][j] = max<int>(next[dp[i][j]][0], dp[i - 1][j]);
                }
                if (j != 0)
                {
                    dp[i][j - 1] = max<int>(next[dp[i][j]][1], dp[i][j  -1]);
                }
            }
        }
    }

    return dp[0][0] == n;
}

int bs()
{
    int a = 2;
    int b = 1000000000;

    int res = -1;
    while (a <= b)
    {
        int mid = (a + b) / 2;
        if (poss(mid))
        {
            res = mid;
            b = mid - 1;
        } else
        {
            a = mid + 1;
        }
    }

    return res;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> p >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    if (p + q >= n)
    {
        cout << 1 << "\n";
        return 0;
    }
    sort(a, a + n);

    cout << bs() << "\n";
}

/*
3 1 1
2
11
17
*/

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