oj.uz

Submission #145182

# Submission time Handle Problem Language Result Execution time Memory
145182 2019-08-19T08:23:57 Z solimm4sks Watching (JOI13_watching) C++14
50 / 100
 467 ms 31964 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 = 0; 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] = ind1;
        bigReach[i] = ind2;
    }

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

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

    if(dp[n - 1][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 = 0; i < n; ++i){
        cin >> a[i];
    }

    sort(a, a + n);

    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 764 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 368 ms 31864 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 451 ms 31864 KB Output is correct
4 Correct 450 ms 31844 KB Output is correct
5 Correct 467 ms 31848 KB Output is correct
6 Correct 446 ms 31864 KB Output is correct
7 Correct 442 ms 31908 KB Output is correct
8 Correct 450 ms 31864 KB Output is correct
9 Correct 451 ms 31864 KB Output is correct
10 Correct 448 ms 31836 KB Output is correct
11 Correct 443 ms 31964 KB Output is correct
12 Correct 455 ms 31860 KB Output is correct
13 Correct 418 ms 31864 KB Output is correct
14 Correct 428 ms 31864 KB Output is correct
15 Correct 433 ms 31864 KB Output is correct