oj.uz

Submission #499178

# Submission time Handle Problem Language Result Execution time Memory
499178 2021-12-27T11:54:21 Z khoabright Watching (JOI13_watching) C++17
50 / 100
 422 ms 31820 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()

int n, P, Q;
vector<int> a;
const int N = 2005;
const int inf = 1e15;
int L[N][2];
int dp[N][N];

bool check(int w) {
    rep(i, 0, n + 2) rep(j, 0, n + 2) {
        dp[i][j] = inf;
    }

    rep(i, 1, n) {
        L[i][0] = lower_bound(all1(a), a[i] - w + 1) - a.begin();
        L[i][1] = lower_bound(all1(a), a[i] - 2 * w + 1) - a.begin();
    }

//    rep(i, 1, n) {
//        cout << L[i][0] << ' ' << L[i][1] << '\n';
//    }

    rep(i, 0, P) dp[0][i] = 0;

    rep(i, 1, n) rep(p, 1, P) {
        dp[i][p] = min(dp[L[i][0] - 1][p - 1], dp[L[i][1] - 1][p] + 1);
        //cout<<"i,p,dp="<<i<<' '<<p<<' '<<dp[i][p]<<'\n';
        //if (dp[i][p] <= Q) return 1;
    }

    return dp[n][P] <= Q;
}

void solve() {
    cin >> n >> P >> Q;
    P = min(P, n);
    //Q = min(Q, n);
    a.resize(n + 1);
    rep(i, 1, n) cin >> a[i];
    sort(all1(a));

   // cout << check(3) << '\n';
    int l = 1, r = inf, ans = 0;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (check(m)) {
            ans = m, r = m - 1;
        }
        else l = m + 1;
    }

    assert(ans > 0);
    cout << ans;
}

main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}

Compilation message

watching.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main() {
      | ^~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 31784 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 409 ms 31788 KB Output is correct
4 Correct 416 ms 31788 KB Output is correct
5 Correct 213 ms 31788 KB Output is correct
6 Correct 422 ms 31812 KB Output is correct
7 Correct 206 ms 31788 KB Output is correct
8 Correct 220 ms 31692 KB Output is correct
9 Correct 307 ms 31820 KB Output is correct
10 Correct 421 ms 31788 KB Output is correct
11 Correct 219 ms 31788 KB Output is correct
12 Correct 332 ms 31692 KB Output is correct
13 Correct 199 ms 31784 KB Output is correct
14 Correct 213 ms 31792 KB Output is correct
15 Incorrect 201 ms 31752 KB Output isn't correct