oj.uz

Submission #499228

# Submission time Handle Problem Language Result Execution time Memory
499228 2021-12-27T13:27:15 Z khoabright Watching (JOI13_watching) C++17
100 / 100
 243 ms 16076 KB 
#include <bits/stdc++.h>
using namespace std;
 
#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 = 1e9;
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, 0, P) {
        dp[i][p] = min((p > 0 ? dp[L[i][0] - 1][p - 1] : inf), dp[L[i][1] - 1][p] + 1);
        //cout<<"i,p,dp="<<i<<' '<<p<<' '<<dp[i][p]<<'\n';
    }
 
    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;
    }
    cout << ans;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    solve();
}

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 320 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 696 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 700 KB Output is correct
11 Correct 1 ms 700 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 704 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 15996 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 199 ms 16076 KB Output is correct
4 Correct 243 ms 16076 KB Output is correct
5 Correct 78 ms 16076 KB Output is correct
6 Correct 233 ms 16060 KB Output is correct
7 Correct 71 ms 16052 KB Output is correct
8 Correct 82 ms 16048 KB Output is correct
9 Correct 145 ms 16068 KB Output is correct
10 Correct 240 ms 16076 KB Output is correct
11 Correct 80 ms 15948 KB Output is correct
12 Correct 159 ms 15940 KB Output is correct
13 Correct 74 ms 16072 KB Output is correct
14 Correct 74 ms 16076 KB Output is correct
15 Correct 74 ms 16076 KB Output is correct