oj.uz

Submission #976681

# Submission time Handle Problem Language Result Execution time Memory
976681 2024-05-07T02:45:07 Z vjudge1 Watching (JOI13_watching) C++17
100 / 100
 619 ms 31940 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lld double
#define int ll
#define usaco(fname) freopen(#fname ".in","r",stdin);freopen(#fname ".out","w",stdout);
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
// const ll INF = 1e18;
const int INF = 1e18;
const int mod = 1e9+7;
const lld PI = acos(-1.0);
int di[] = {1, -1, 0, 0, 1, 1, -1, -1};
int dj[] = {0, 0, 1, -1, 1, -1, 1, -1};
#define debug(x) cout << #x << ": " << x << endl;
#define add(a, b) a += b, a %= mod
#define mul(a, b) ((a % mod) * (b % mod)) % mod
#define all(x) x.begin(),x.end()

void solve() {
  int n,p,q;cin>>n>>p>>q;
  vector<int> a(n);
  for (int i =0 ; i < n; i++) cin >> a[i];
  sort(all(a));

  int Q = min(q, n);
  function<bool(int)> chk = [&](int k) {
    // dp[i][q]
    vector<vector<int>> dp(n, vector<int>(Q+1, INF));
    for (int i = 0; i < n; i++) {
      // we use K or 2*K here
      int j1 = lower_bound(all(a), a[i] + k) - a.begin();j1--;
      int j2 = lower_bound(all(a), a[i] + 2*k) - a.begin();j2--;

      for (int j = 0; j <= Q; j++) {
        int before = (i-1 >= 0 ? dp[i-1][j] : 0);
        // for addition of P
        dp[j1][j] = min(dp[j1][j], before + 1);

        if (j+1 <= Q) dp[j2][j+1] = min(dp[j2][j+1], before);
      }
    }

    for (int i = 0; i <= Q; i++) {
      if (dp[n-1][i] <= p) return true;
    }
    return false;
  };

  int ans = 1e9+69;
  int l = 1, r = 1e9+69;
  while (l <= r) {
    int mid = (l+r)>>1;

    if (chk(mid)) {
      r = mid-1;
      ans = mid;
    } else l = mid+1;
  }

  cout << ans << endl;
}

int32_t main() {
  ios_base::sync_with_stdio(0);cin.tie(0);
  int t=1;
  while(t--) solve();

  return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 356 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 600 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 430 ms 24144 KB Output is correct
4 Correct 23 ms 1860 KB Output is correct
5 Correct 572 ms 31936 KB Output is correct
6 Correct 619 ms 31940 KB Output is correct
7 Correct 8 ms 604 KB Output is correct
8 Correct 216 ms 12448 KB Output is correct
9 Correct 34 ms 2500 KB Output is correct
10 Correct 27 ms 1996 KB Output is correct
11 Correct 576 ms 30420 KB Output is correct
12 Correct 289 ms 16232 KB Output is correct
13 Correct 10 ms 844 KB Output is correct
14 Correct 8 ms 796 KB Output is correct
15 Correct 10 ms 816 KB Output is correct