oj.uz

Submission #958348

# Submission time Handle Problem Language Result Execution time Memory
958348 2024-04-05T13:32:15 Z JwFXoiz Watching (JOI13_watching) C++14
100 / 100
 570 ms 31432 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define inf 0x3F3F3F3F

const int MXN = 2e3 + 5;

int n, p, q;
int a[MXN];
int dp[MXN][MXN];

int need(int val)
{
    for (int i = 0; i <= p; i++) 
    {
        int k1 = 0, k2 = 0;
        for (int j = 1; j <= n; j++) 
        {
            dp[i][j] = inf;
            while (k1 + 1 <= n && a[k1 + 1] <= a[j] - val) k1++;
            while (k2 + 1 <= n && a[k2 + 1] <= a[j] - 2 * val) k2++;
            dp[i][j] = dp[i][k2] + 1;
            if (i) dp[i][j] = min(dp[i][j], dp[i - 1][k1]);
        }
    }
    return dp[p][n];
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> p >> q;
    if (p >= n || q >= n)
    {
        cout << 1 << '\n';
        return 0;
    }
    p = min(p, n), q = min(q, n);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int l = 1, r = 1e9;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (need(mid) > q) l = mid + 1;
        else r = mid;
    }
    cout << l << '\n';
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 464 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 454 ms 25284 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 6 ms 2652 KB Output is correct
8 Correct 42 ms 2652 KB Output is correct
9 Correct 257 ms 12892 KB Output is correct
10 Correct 570 ms 31432 KB Output is correct
11 Correct 28 ms 2652 KB Output is correct
12 Correct 296 ms 17072 KB Output is correct
13 Correct 4 ms 2652 KB Output is correct
14 Correct 5 ms 2732 KB Output is correct
15 Correct 5 ms 2652 KB Output is correct