oj.uz

Submission #963512

# Submission time Handle Problem Language Result Execution time Memory
963512 2024-04-15T07:53:37 Z BhavayGoyal Watching (JOI13_watching) C++14
100 / 100
 318 ms 32200 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using oset = 
            tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const int linf = 1e18;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


// -------------------------------------------------- Main Code --------------------------------------------------

int dp[2005][2005];
int n, nxtP[2005], nxtQ[2005], arr[2005];

int sol(int idx, int p) {
    if (idx >= n) return 0;
    if (dp[idx][p] != -1) return dp[idx][p];
    int ans = inf;
    if (p) ans = min(ans, sol(nxtP[idx]+1, p-1));
    ans = min(ans, sol(nxtQ[idx]+1, p) + 1);
    return dp[idx][p] = ans;
}

void sol() {
    int p, q; cin >> n >> p >> q;
    p = min(p, n); q = min(q, n);

    for (int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr+n);

    auto fiss = [&](int mid) {
        for (int i = 0; i <= n; i++) for (int j = 0; j <= p; j++) dp[i][j] = -1;
        for (int i = 0; i < n; i++) {
            nxtP[i] = upper_bound(arr, arr+n, arr[i]+mid-1) - arr - 1;
            nxtQ[i] = upper_bound(arr, arr+n, arr[i]+2*mid-1) - arr - 1;
        }
        
        return (sol(0, p) <= q);
    };

    int i = 1, j = inf, ans = inf;
    while (i <= j) {
        int mid = (i+j)/2;
        if (fiss(mid)) ans = mid, j = mid-1;
        else i = mid+1;
    }
    cout << ans << endl;
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t; 
    while (t--) {
        sol();
    }
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 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 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31320 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 268 ms 32196 KB Output is correct
4 Correct 282 ms 32084 KB Output is correct
5 Correct 28 ms 31580 KB Output is correct
6 Correct 295 ms 32200 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 30 ms 31508 KB Output is correct
9 Correct 94 ms 31580 KB Output is correct
10 Correct 318 ms 31916 KB Output is correct
11 Correct 37 ms 31580 KB Output is correct
12 Correct 211 ms 32080 KB Output is correct
13 Correct 9 ms 31324 KB Output is correct
14 Correct 11 ms 31484 KB Output is correct
15 Correct 9 ms 31324 KB Output is correct