oj.uz

Submission #145180

# Submission time Handle Problem Language Result Execution time Memory
145180 2019-08-19T08:13:07 Z solimm4sks Watching (JOI13_watching) C++14
50 / 100
 448 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 10000

bool check(long long w){
    for(long long i = 0; i < n; ++i){
        for(long long j = 0; j <= p; ++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 <= p; ++i){
        dp[0][i] = 0;
    }
    dp[0][0] = 1;

    for(long long i = 1; i < n; ++i){
        for(long long j = 0; j <= p; ++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 = 1000000000;
    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;
        }
    }

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

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 13 ms 8440 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 344 ms 31844 KB Output is correct
4 Correct 448 ms 31964 KB Output is correct
5 Correct 32 ms 9720 KB Output is correct
6 Correct 448 ms 31884 KB Output is correct
7 Correct 17 ms 8696 KB Output is correct
8 Correct 40 ms 10620 KB Output is correct
9 Correct 169 ms 20344 KB Output is correct
10 Correct 440 ms 31852 KB Output is correct
11 Correct 34 ms 9852 KB Output is correct
12 Correct 216 ms 23900 KB Output is correct
13 Correct 18 ms 8696 KB Output is correct
14 Correct 21 ms 8824 KB Output is correct
15 Correct 21 ms 8700 KB Output is correct