Submission #51437

#	Time	Username	Problem	Language	Result	Execution time	Memory
51437		combi2k2	Watching (JOI13_watching)	C++14	100 / 100	81 ms	8956 KiB

watching

#include<bits/stdc++.h>
using namespace std;
const int N = 2001;
int n, p, q;
int a[N], f[N][2];
int dp[N][N];
int BS(int l,int r,int val) {
    if(l == r)  return l;
    int m = (l + r) / 2;
    if(a[m] > val)  return BS(l,m,val);
    return BS(m + 1,r,val);
}
bool ch(int w)   {
    for(int i = 1 ; i <= n ; ++i)   {
        f[i][0] = BS(1,n + 1,a[i] + w - 1) - 1;
        f[i][1] = BS(1,n + 1,a[i] + w * 2 - 1) - 1;
    }
    for(int i = 0 ; i <= p ; ++i)
    for(int j = 0 ; j <= q ; ++j)    {
        dp[i][j] = 0;
        if(i == 0 && j == 0)    continue;
        if(i > 0)   {
            int k = dp[i - 1][j] + 1;
            dp[i][j] = max(dp[i][j],f[k][0]);
        }
        if(j > 0)   {
            int k = dp[i][j - 1] + 1;
            dp[i][j] = max(dp[i][j],f[k][1]);
        }
        if(dp[i][j] == n)   return 1;
    }
    return 0;
}
int main()  {
    ios_base::sync_with_stdio(false);   cin.tie(0);
    cin >> n >> p >> q;
    if(p + q >= n)  {   cout << "1";    exit(0);    }
    for(int i = 1 ; i <= n ; ++i)
        cin >> a[i];
    sort(a + 1,a + 1 + n);
    int L = 1, R = 1e9;
    while(L != R)   {
        int M = (L + R) / 2;
        if(ch(M))   R = M;
        else        L = M + 1;
    }
    cout << L << endl;
}

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