Submission #274728

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
274728	2020-08-19T14:46:16 Z	bicsi	Watching (JOI13_watching)	C++14	100 / 100	197 ms	15276 KB

watching

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, p, q; cin >> n >> p >> q;

  if (p + q >= n) {
    cout << 1 << endl;
    return 0;
  }

  vector<int> a(n);
  for (int i = 0; i < n; ++i) 
    cin >> a[i]; 
  sort(a.begin(), a.end());

  auto ok = [&](int w) -> bool {
    int ps = 0, pl = 0;
    vector<vector<int>> dp(n + 1, vector<int>(p + 1, n + 1));
    fill(dp[0].begin(), dp[0].end(), 0);
    for (int i = 0; i < n; ++i) {
      while (a[ps] <= a[i] - w) ++ps;
      while (a[pl] <= a[i] - 2 * w) ++pl;

      for (int j = 0; j <= p; ++j) {
        if (j > 0) dp[i + 1][j] = min(dp[i + 1][j], dp[ps][j - 1]);
        dp[i + 1][j] = min(dp[i + 1][j], dp[pl][j] + 1);
      }
    }
    return dp[n][p] <= q;
  };
  
  int ans = 0, adv = 1;
  for (int step = 1; step; adv ? step *= 2 : step /= 2) {
    if (ok(ans + step)) adv = 0;
    else ans += step;
  }
  cout << ans + 1 << '\n';

  return 0;
}

Subtask #1

50.0 / 50.0

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

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	384 KB	Output is correct
2	Correct	1 ms	376 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	12 ms	512 KB	Output is correct
8	Correct	33 ms	1512 KB	Output is correct
9	Correct	197 ms	6440 KB	Output is correct
10	Correct	52 ms	15276 KB	Output is correct
11	Correct	7 ms	1152 KB	Output is correct
12	Correct	46 ms	8188 KB	Output is correct
13	Correct	9 ms	568 KB	Output is correct
14	Correct	13 ms	512 KB	Output is correct
15	Correct	14 ms	524 KB	Output is correct