oj.uz

Submission #278219

# Submission time Handle Problem Language Result Execution time Memory
278219 2020-08-21T11:19:51 Z erray Watching (JOI13_watching) C++17
0 / 100
 586 ms 15564 KB 
// author: erray
#include<bits/stdc++.h>
 
using namespace std;

template<typename T, typename F> string to_string(pair<T, F> p);
string to_string(string s) {
  return '"' + s + '"';
}
string to_string(char c) {
  return (string) "'" + c + "'";
}
string to_string(const char* p) {
  return to_string((string) p);
}
string to_string(bool B) {
  return (B ? "true" : "false");
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = 0; i < (int) v.size(); ++i) {
    if ((int) res.size() > 1) res += ", ";
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template<size_t T> string to_string(bitset<T> bs) {
  return bs.to_string();
}
template<typename T> string to_string(T v) {
  string res = "{";
  for (auto& el : v) {
    if ((int) res.size() > 1) res += ", ";
    res += to_string(el);
  }
  res += "}";
  return res;
}
template<typename T, typename F> string to_string(pair<T, F> p) {
  return '(' + to_string(p.first) + ", " + to_string(p.second) + ')';
}
void debug_out() {
  cerr << endl;
}
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:" , debug_out(__VA_ARGS__)
#else
#define debug(...) (void) 37
#endif
 
int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, p, q;
  cin >> n >> p >> q;
  if (p + q >= n) return cout << 1, 0;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  sort(a.begin(), a.end());
  auto check = [&](int l) {
    vector<vector<int>> dp(n, vector<int>(p + 1, INT_MAX));
    auto get = [&](int x, int y) {
      if (y > p) return (int) 1e9;
      if (x == n) return 0;
      return dp[x][y];
    };
    int p1 = n - 1, p2 = n - 1;
    for (int i = n - 1; i >= 0; --i) {
      while (p1 > 0 && a[p1] > a[i] + l) --p1;
      while (p2 > 0 && a[p2] > a[i] + 2 * l) --p2;
      for (int j = 0; j <= p; ++j) {
        dp[i][j] = get(p1 + 1, j + 1);
        dp[i][j] = min(dp[i][j], get(p2 + 1, j) + 1);
      }
    }
    return dp[0][0] <= q;
  };
  int s = 1, e = (int) 1e9;
  while (s != e) {
    int mid = (s + e) >> 1;
    if (check(mid)) e = mid;
    else s = mid + 1;    
    debug(s, e);
  }
  cout << s + 1 << '\n';
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 7 ms 544 KB Output is correct
8 Correct 48 ms 1464 KB Output is correct
9 Correct 224 ms 6424 KB Output is correct
10 Correct 586 ms 15564 KB Output is correct
11 Correct 30 ms 1180 KB Output is correct
12 Incorrect 294 ms 8196 KB Output isn't correct
13 Halted 0 ms 0 KB -