Submission #274728

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
274728	2020-08-19 14:46:16	bicsi	구경하기 (JOI13_watching)	C++14	100 / 100	197 ms	15276 KiB

watching

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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);
      }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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