oj.uz

Submission #843766

# Submission time Handle Problem Language Result Execution time Memory
843766 2023-09-04T14:27:25 Z kitsune Watching (JOI13_watching) C++14
100 / 100
 140 ms 16212 KB 
#include <bits/stdc++.h>
/// kitsune
using namespace std;

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp &__a, const _Tp &__b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp &__a, const _Tp &__b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 2e3 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "1";

int n, a, b;
int p[siz];
int dp[siz][siz];

bool check(int w) {
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    rep (i, 1, n) {
        int j_1 = lower_bound(p + 1, p + n + 1, p[i] - w + 1) - p - 1;
        int j_2 = lower_bound(p + 1, p + n + 1, p[i] - 2 * w + 1) - p - 1;
        rep (k, 0, a) {
            if (k > 0) {
                minimize(dp[i][k], dp[j_1][k - 1]);
            }
            minimize(dp[i][k], dp[j_2][k] + 1);
        }
    }

    rep (k, 0, a) {
        if (dp[n][k] <= b) {
            return true;
        }
    }

    return false;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen((file + ".inp").c_str(), "r", stdin);
//    freopen((file + ".out").c_str(), "w", stdout);

    cin >> n >> a >> b;

    minimize(a, n);
    minimize(b, n);

    rep (i, 1, n) {
        cin >> p[i];
    }

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

    int ans = -1;
    for (int lb = 1, rb = 1e9; lb <= rb; ) {
        int mb = (lb + rb) / 2;

        if (check(mb)) {
            ans = mb;
            rb = mb - 1;
        } else {
            lb = mb + 1;
        }
    }

    cout << ans << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16212 KB Output is correct
2 Correct 20 ms 15964 KB Output is correct
3 Correct 23 ms 15964 KB Output is correct
4 Correct 14 ms 15964 KB Output is correct
5 Correct 14 ms 15964 KB Output is correct
6 Correct 17 ms 15964 KB Output is correct
7 Correct 14 ms 15964 KB Output is correct
8 Correct 15 ms 15964 KB Output is correct
9 Correct 15 ms 15964 KB Output is correct
10 Correct 13 ms 15964 KB Output is correct
11 Correct 15 ms 15964 KB Output is correct
12 Correct 26 ms 15972 KB Output is correct
13 Correct 20 ms 15964 KB Output is correct
14 Correct 17 ms 15964 KB Output is correct
15 Correct 14 ms 15964 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15964 KB Output is correct
2 Correct 13 ms 15964 KB Output is correct
3 Correct 108 ms 16152 KB Output is correct
4 Correct 116 ms 16148 KB Output is correct
5 Correct 29 ms 15964 KB Output is correct
6 Correct 115 ms 16148 KB Output is correct
7 Correct 19 ms 15964 KB Output is correct
8 Correct 27 ms 15964 KB Output is correct
9 Correct 78 ms 16168 KB Output is correct
10 Correct 140 ms 15964 KB Output is correct
11 Correct 25 ms 15964 KB Output is correct
12 Correct 78 ms 15964 KB Output is correct
13 Correct 20 ms 15964 KB Output is correct
14 Correct 27 ms 15964 KB Output is correct
15 Correct 22 ms 15964 KB Output is correct