oj.uz

Submission #499174

# Submission time Handle Problem Language Result Execution time Memory
499174 2021-12-27T11:46:35 Z khoabright Watching (JOI13_watching) C++17
50 / 100
 455 ms 31812 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);

    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;
    }
    cout << ans;
}

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

Compilation message

watching.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | 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 204 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 2 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 1 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 213 ms 31812 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 378 ms 31776 KB Output is correct
4 Correct 415 ms 31788 KB Output is correct
5 Correct 208 ms 31692 KB Output is correct
6 Correct 407 ms 31784 KB Output is correct
7 Correct 201 ms 31796 KB Output is correct
8 Correct 219 ms 31784 KB Output is correct
9 Correct 294 ms 31792 KB Output is correct
10 Correct 455 ms 31784 KB Output is correct
11 Correct 219 ms 31792 KB Output is correct
12 Correct 337 ms 31792 KB Output is correct
13 Correct 211 ms 31784 KB Output is correct
14 Correct 207 ms 31796 KB Output is correct
15 Incorrect 216 ms 31788 KB Output isn't correct