oj.uz

Submission #502676

# Submission time Handle Problem Language Result Execution time Memory
502676 2022-01-06T12:34:17 Z evenvalue Watching (JOI13_watching) C++17
100 / 100
 627 ms 16084 KB 
#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.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 459 ms 12168 KB Output is correct
4 Correct 608 ms 16084 KB Output is correct
5 Correct 27 ms 972 KB Output is correct
6 Correct 627 ms 16076 KB Output is correct
7 Correct 6 ms 460 KB Output is correct
8 Correct 41 ms 1356 KB Output is correct
9 Correct 241 ms 6316 KB Output is correct
10 Correct 576 ms 15288 KB Output is correct
11 Correct 29 ms 1100 KB Output is correct
12 Correct 299 ms 8012 KB Output is correct
13 Correct 6 ms 460 KB Output is correct
14 Correct 8 ms 588 KB Output is correct
15 Correct 7 ms 564 KB Output is correct