Submission #306335

#	Time	Username	Problem	Language	Result	Execution time	Memory
306335		syy	Watching (JOI13_watching)	C++17	50 / 100	1084 ms	32012 KiB

watching

#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 / 50
• Subtask 2: 0 / 50