Submission #764648

#	Time	Username	Problem	Language	Result	Execution time	Memory
764648		ind1v	Watching (JOI13_watching)	C++11	50 / 100	1073 ms	16216 KiB

watching

#include <bits/stdc++.h>

using namespace std;

const int N = 2005;

int n, p, q;
long long a[N];
int dp[N][N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> p >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  if (p + q >= n) {
    cout << 1;
    exit(0);
  }
  sort(a + 1, a + n + 1);
  a[0] = numeric_limits<long long>::min();
  int l = 1, r = 1000000000, ans = -1;
  while (l <= r) {
    int m = l + r >> 1;
    memset(dp, 0x3f, sizeof(dp));
    for (int j = 0; j <= q; j++) {
      dp[0][j] = 0;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= q; j++) {
        int prv = upper_bound(a, a + n + 1, a[i] - m) - a;
        dp[i][j] = min(dp[i][j], 1 + dp[prv - 1][j]);
        if (j > 0) {
          prv = upper_bound(a, a + n + 1, a[i] - 2 * m) - a;
          dp[i][j] = min(dp[i][j], dp[prv - 1][j - 1]);
        }
      }
    }
    if (dp[n][q] <= p) {
      ans = m;
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  cout << ans;
  return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int m = l + r >> 1;
      |             ~~^~~

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