oj.uz

Submission #102825

# Submission time Handle Problem Language Result Execution time Memory
102825 2019-03-27T16:55:31 Z popovicirobert Watching (JOI13_watching) C++14
100 / 100
 990 ms 16140 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x))

using namespace std;

const ll INF = 1e15;
const int MAXN = 2005;

int dp[MAXN + 1][MAXN + 1];
ll arr[MAXN + 1];

int nxt_a[MAXN + 1], nxt_b[MAXN + 1];

inline bool check(ll w, int n, int a, int b) {
    int i, j;
    for(i = 0; i <= n; i++) {
        for(j = i; j <= n + 1; j++) {
            if(arr[j] - arr[i] >= w) {
                nxt_a[i] = j;
                break;
            }
        }
        for(j = i; j <= n + 1; j++) {
            if(arr[j] - arr[i] >= 2LL * w) {
                nxt_b[i] = j;
                break;
            }
        }
    }
    dp[0][0] = 1;
    for(int s = 1; s <= a + b; s++) {
        for(i = 0; i <= min(a, s); i++) {
            j = s - i;
            if(j > b) {
                continue;
            }
            dp[i][j] = 0;
            if(i > 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                dp[i][j] = max(dp[i][j], nxt_a[dp[i - 1][j]]);
            }
            if(j > 0) {
                dp[i][j] = max(dp[i][j], dp[i][j - 1]);
                dp[i][j] = max(dp[i][j], nxt_b[dp[i][j - 1]]);
            }
        }
    }
    return dp[a][b] == n + 1;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, a, b;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> a >> b;
    for(i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    sort(arr + 1, arr + n + 1);
    arr[n + 1] = INF;
    a = min(n, a), b = min(b, n);
    int res = 0;
    for(int step = 1 << 29; step; step >>= 1) {
        if(check(res + step, n, a, b) == 0) {
            res += step;
        }
    }
    cout << res + 1;
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 428 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 438 ms 12300 KB Output is correct
4 Correct 105 ms 8952 KB Output is correct
5 Correct 33 ms 1024 KB Output is correct
6 Correct 990 ms 16140 KB Output is correct
7 Correct 25 ms 384 KB Output is correct
8 Correct 27 ms 1280 KB Output is correct
9 Correct 39 ms 3712 KB Output is correct
10 Correct 66 ms 8704 KB Output is correct
11 Correct 38 ms 1152 KB Output is correct
12 Correct 187 ms 8084 KB Output is correct
13 Correct 35 ms 512 KB Output is correct
14 Correct 22 ms 512 KB Output is correct
15 Correct 18 ms 504 KB Output is correct