Submission #379552

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
379552	2021-03-18 14:37:55	penguin133	Watching (JOI13_watching)	C++14	100 / 100	250 ms	16236 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 n,p,q,s = 1, e= 1e9 + 5, ans = 1e9 + 5;
int dp[2005][2005], A[2005];
bool c(int x){
  for(int i=1;i<=n;i++){
    int l = 1, r = 1;
    while(A[i] - A[l] >= x)l++;
    while(A[i] - A[r] >= 2*x)r++;
    for(int j=0;j<=p;j++){
      if(j == 0)dp[i][j] = dp[r-1][j] + 1;
      else dp[i][j] = min(dp[l-1][j-1], dp[r-1][j] + 1);
    }
  }
  return dp[n][p] <= q;
}
int main(){
  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);
  while(s <= e){
    int m = (s + e)/2;
    memset(dp, 0, sizeof(dp));
    if(c(m)){
      ans = m;
      e = m - 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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