oj.uz

Submission #499171

# Submission time Handle Problem Language Result Execution time Memory
499171 2021-12-27T11:44:23 Z khoabright Watching (JOI13_watching) C++17
50 / 100
 178 ms 16084 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, 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;
    }
    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 700 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 704 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 700 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 704 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 69 ms 15948 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 164 ms 15948 KB Output is correct
4 Correct 178 ms 16084 KB Output is correct
5 Correct 75 ms 16076 KB Output is correct
6 Correct 175 ms 16064 KB Output is correct
7 Correct 72 ms 16056 KB Output is correct
8 Correct 89 ms 16072 KB Output is correct
9 Correct 117 ms 16060 KB Output is correct
10 Correct 176 ms 16060 KB Output is correct
11 Correct 95 ms 16076 KB Output is correct
12 Correct 141 ms 16056 KB Output is correct
13 Correct 71 ms 16072 KB Output is correct
14 Correct 72 ms 15948 KB Output is correct
15 Incorrect 73 ms 16076 KB Output isn't correct