oj.uz

Submission #306335

# Submission time Handle Problem Language Result Execution time Memory
306335 2020-09-25T09:08:13 Z syy Watching (JOI13_watching) C++17
50 / 100
 1000 ms 32012 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, p, q, A[2005], w, upper, lower, dp[2005][2005];

ll f(ll index, ll bigCamsNeeded) { //Min p that can cover everything
  if (index < 0) return 0;
  if (dp[index][bigCamsNeeded] != -1) return dp[index][bigCamsNeeded]; //If calculated
  dp[index][bigCamsNeeded] = LLONG_MAX;
  if (bigCamsNeeded > 0) {
    ll ind = upper_bound(A, A + n, A[index] - w - w) - A - 1; //Cannot take
    dp[index][bigCamsNeeded] = f(ind, bigCamsNeeded - 1);
  }
  ll ind = upper_bound(A, A + n, A[index] - w) - A - 1;
  dp[index][bigCamsNeeded] = min(dp[index][bigCamsNeeded], f(ind, bigCamsNeeded) + 1); // You used one more small camera so need + 1
  return dp[index][bigCamsNeeded];
}

int main() {
  cin >> n >> p >> q;
  if (p + q >= n) {
    cout << 1;
    return 0;
  }
  for (ll i = 0; i < n; i++) cin >> A[i];
  sort(A, A + n);
  lower = 0; upper = A[n - 1] + 1;
  while (upper - lower > 1) {
  	memset(dp, -1, sizeof dp); //Not calculated before.
    w = lower + (upper - lower) / 2;
    if (f(n - 1, q) <= p) upper = w;
    else lower = w;
  }
  cout << upper;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 31744 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 159 ms 31864 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 256 KB Output is correct
7 Correct 153 ms 31744 KB Output is correct
8 Correct 162 ms 31864 KB Output is correct
9 Correct 157 ms 31744 KB Output is correct
10 Correct 157 ms 31744 KB Output is correct
11 Correct 152 ms 31736 KB Output is correct
12 Correct 163 ms 31992 KB Output is correct
13 Correct 150 ms 31744 KB Output is correct
14 Correct 151 ms 31872 KB Output is correct
15 Correct 150 ms 31744 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 31872 KB Output is correct
2 Correct 1 ms 256 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 167 ms 31864 KB Output is correct
8 Correct 873 ms 31992 KB Output is correct
9 Correct 400 ms 31992 KB Output is correct
10 Correct 471 ms 32012 KB Output is correct
11 Execution timed out 1084 ms 31992 KB Time limit exceeded
12 Halted 0 ms 0 KB -