Submission #502676

#	Time	Username	Problem	Language	Result	Execution time	Memory
502676		evenvalue	Watching (JOI13_watching)	C++17	100 / 100	627 ms	16084 KiB

watching

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

using int64 = int64_t;
using ld = long double;

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

[[maybe_unused]] int readInt() {
  int x;
  cin >> x;
  return x;
}
[[maybe_unused]] int64 readInt64() {
  int64 x;
  cin >> x;
  return x;
}
[[maybe_unused]] char readChar() {
  char c;
  cin >> c;
  return c;
}
[[maybe_unused]] string readString() {
  string s;
  cin >> s;
  return s;
}
[[maybe_unused]] double readDouble() {
  return stod(readString());
}
[[maybe_unused]] ld readLongDouble() {
  return stold(readString());
}
template<typename T1, typename T2>
[[maybe_unused]] pair<T1, T2> readPair() {
  pair<T1, T2> p;
  cin >> p.first >> p.second;
  return p;
}
template<typename T>
[[maybe_unused]] vector<T> readVec(const int sz) {
  vector<T> v(sz);
  for (T &x : v) {
    cin >> x;
  }
  return v;
}
template<typename T>
[[maybe_unused]] vector<vector<T>> readVecVec(const int n, const int m) {
  vector<vector<T>> a(n);
  for (vector<T> &v : a) {
    v = readVec<T>(m);
  }
  return a;
}

const int64 kInf64 = 2e18 + 10;
const int kInf = 2e9 + 10;
const int kMod = 1e9 + 7;

void solution() {
  const int n = readInt(), p = min(n, readInt()), q = min(n, readInt());
  vector<int> a(n + 1, -kInf);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());

  vector<vector<int>> dp(n + 1, vector<int>(p + 1));

  auto check = [&](const int w) {
    for (int i = 0; i <= p; i++) dp[0][i] = 0;
    queue<int> last_p, last_q;
    last_p.push(0), last_q.push(0);
    for (int i = 1; i <= n; i++) {
      last_p.push(i), last_q.push(i);
      while (a[last_p.front()] <= a[i] - w) {
        last_p.pop();
      }
      while (a[last_q.front()] <= a[i] - 2 * w) {
        last_q.pop();
      }
      const int lp = last_p.front(), lq = last_q.front();
      dp[i][0] = dp[lq - 1][0] + 1;
      for (int j = 1; j <= p; j++) {
        const int op1 = dp[lp - 1][j - 1];
        const int op2 = dp[lq - 1][j] + 1;
        dp[i][j] = min(op1, op2);
      }
    }
    return (dp[n][p] <= q);
  };

  int lo = 1, hi = 1e9;
  while (lo < hi) {
    const int mid = (lo + hi) / 2;
    if (check(mid)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  cout << lo << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  const auto begin = std::chrono::high_resolution_clock::now();

//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);

  int t = 1;
  //cin >> t;
  for (int tc = 1; tc <= t; tc++) {
    solution();
  }

  const auto end = std::chrono::high_resolution_clock::now();
  const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
  cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50