oj.uz

Submission #145185

# Submission time Handle Problem Language Result Execution time Memory
145185 2019-08-19T08:28:16 Z solimm4sks Watching (JOI13_watching) C++14
50 / 100
 428 ms 31992 KB 
#include <bits/stdc++.h>
using namespace std;

long long n, p, q;
long long a[200005];
long long dp[2005][2005];

long long smallReach[2005];
long long bigReach[2005];

#define INF 1000000

bool check(long long w){
    for(long long i = 0; i <= n; ++i){
        for(long long j = 0; j <= n; ++j){
            dp[i][j] = INF;
        }
    }

    for(long long i = 1; i <= n; ++i){
        long long ind1 = lower_bound(a, a + n, a[i] - w + 1) - a;
        long long ind2 = lower_bound(a, a + n, a[i] - 2 * w + 1) - a;

        smallReach[i] = max(ind1, 1LL);
        bigReach[i] = max(ind2, 1LL);
    }

    for(long long i = 0; i <= n; ++i){
        dp[0][i] = 0;
    }

    for(long long i = 1; i <= n; ++i){
        for(long long j = 0; j <= n; ++j){
            if(j){
                dp[i][j] = min(dp[bigReach[i] - 1][j] + 1, dp[smallReach[i] - 1][j - 1]);
            }else{
                dp[i][0] = dp[bigReach[i] - 1][0] + 1;
            }
        }
    }

    if(dp[n][p] <= q){
        return true;
    }
    return false;
}


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

    cin >> n >> p >> q;
    for(long long i = 1; i <= n; ++i){
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    p = min(p, n);
    q = min(q, n);

    long long l = 0;
    long long r = 1000000010;
    long long lc = -1;
    while(l <= r){
        long long mid = (l + r) / 2;
        bool ch = check(mid);
        if(ch){
            r = mid - 1;
            lc = mid;
        }else{
            l = mid + 1;
        }
    }

    if(lc == -1){
        while(1);
    }

    cout << lc << "\n";
    return 0;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 31868 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 397 ms 31864 KB Output is correct
4 Correct 393 ms 31864 KB Output is correct
5 Correct 404 ms 31868 KB Output is correct
6 Correct 399 ms 31864 KB Output is correct
7 Correct 422 ms 31864 KB Output is correct
8 Correct 396 ms 31992 KB Output is correct
9 Correct 423 ms 31868 KB Output is correct
10 Correct 428 ms 31864 KB Output is correct
11 Correct 403 ms 31864 KB Output is correct
12 Correct 391 ms 31992 KB Output is correct
13 Correct 398 ms 31992 KB Output is correct
14 Correct 401 ms 31864 KB Output is correct
15 Correct 402 ms 31868 KB Output is correct