oj.uz

Submission #757761

# Submission time Handle Problem Language Result Execution time Memory
757761 2023-06-13T17:51:14 Z taher Watching (JOI13_watching) C++17
100 / 100
 20 ms 364 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n , p , q;
  cin >> n >> p >> q;
  vector<int> a(n);
  for (int i = 0 ; i < n ; i++) {
    cin >> a[i];
  }
  if (p + q >= n) {
    cout << 1 << '\n';
    return 0;
  }
  sort(a.begin() , a.end());
  auto can = [&](long long w) {
    #define a3 array<int , 3>
    #define pi pair<int , int>
    const long long inf = (long long)1e18;
    vector<long long> d(n + 1 , -inf);
    d[0] = p * w + q * w * 2;
    priority_queue<a3> pq;
    pq.push({0 , p , q});
    while (!pq.empty()) {
      auto f = pq.top();
      pq.pop();
      int who = f[0] , cur_p = f[1] , cur_q = f[2];
      if (who == n) return true;
      long long val = cur_p * w + cur_q * w * 2;
      if (val != d[who]) continue;
      if (cur_q > 0) {
        int new_id = lower_bound(a.begin() , a.end() , a[who] + w * 2) - a.begin();
        long long new_val = val - 2 * w;
        if (d[new_id] < new_val) {
          d[new_id] = new_val;
          pq.push({new_id , cur_p , cur_q - 1});
        }
      }
      if (cur_p > 0) {
        int new_id = lower_bound(a.begin() , a.end() , a[who] + w) - a.begin();
        long long new_val = val - w;
        if (d[new_id] < new_val) {
          d[new_id] = new_val;
          pq.push({new_id , cur_p - 1 , cur_q});
        }
      }
    }
    return false;
  };
  int l = 0 , r = (int)1e9 + 1;
  int best = (int)1e9 + 1;
  while (l <= r) {
    int mid = l + (r - l) / 2;
    if (can(mid)) {
      r = mid - 1;
      best = mid;
    }
    else l = mid + 1;
  }
  cout << best << '\n';
  return 0; 
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 20 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 4 ms 348 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct