oj.uz

Submission #51437

# Submission time Handle Problem Language Result Execution time Memory
51437 2018-06-18T02:23:49 Z combi2k2 Watching (JOI13_watching) C++14
100 / 100
 81 ms 8956 KB 
#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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 520 KB Output is correct
6 Correct 2 ms 556 KB Output is correct
7 Correct 2 ms 556 KB Output is correct
8 Correct 2 ms 616 KB Output is correct
9 Correct 2 ms 696 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 3 ms 880 KB Output is correct
12 Correct 2 ms 892 KB Output is correct
13 Correct 2 ms 892 KB Output is correct
14 Correct 2 ms 892 KB Output is correct
15 Correct 2 ms 892 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 892 KB Output is correct
2 Correct 2 ms 892 KB Output is correct
3 Correct 2 ms 892 KB Output is correct
4 Correct 3 ms 892 KB Output is correct
5 Correct 2 ms 892 KB Output is correct
6 Correct 3 ms 892 KB Output is correct
7 Correct 6 ms 892 KB Output is correct
8 Correct 21 ms 1532 KB Output is correct
9 Correct 20 ms 3964 KB Output is correct
10 Correct 29 ms 8956 KB Output is correct
11 Correct 15 ms 8956 KB Output is correct
12 Correct 81 ms 8956 KB Output is correct
13 Correct 9 ms 8956 KB Output is correct
14 Correct 10 ms 8956 KB Output is correct
15 Correct 10 ms 8956 KB Output is correct