oj.uz

Submission #328710

# Submission time Handle Problem Language Result Execution time Memory
328710 2020-11-17T18:08:36 Z a_player Watching (JOI13_watching) C++14
100 / 100
 294 ms 16108 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int nax=2e3+3;
int n,p,q;
ll a[nax];
int dp[nax][nax];
bool check(ll w){
  if(w<=0)return false;
  memset(dp,0,sizeof(dp));
  for(int i=0;i<n;i++){
    int ppp=0;
    while(i-ppp>=0&&a[i]-w+1LL<=a[i-ppp])ppp++;
    int pp=0;
    while(i-pp>=0&&a[i]-2LL*w+1<=a[i-pp])pp++;
    for(int j=0;j<=q;j++){
      if(i-ppp<0)dp[i][j]=1;
      else dp[i][j]=dp[i-ppp][j]+1;
      if(j!=0){
      if(i-pp<0)dp[i][j]=0;
      else dp[i][j]=min(dp[i][j],dp[i-pp][j-1]);
    }
    }
  }
  return dp[n-1][q]<=p;
}

int main(){
  cin>>n>>p>>q;
  if(p+q>=n){
    cout<<1<<endl;
    return 0;
  }
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n);
  ll x=-1;
  for(ll b=1e9;b>=1LL;b/=2LL)
  while(!check(x+b))x+=b;
  cout<<x+1<<endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 16108 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 93 ms 15980 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 99 ms 15980 KB Output is correct
8 Correct 95 ms 16108 KB Output is correct
9 Correct 94 ms 15980 KB Output is correct
10 Correct 94 ms 15980 KB Output is correct
11 Correct 75 ms 15980 KB Output is correct
12 Correct 76 ms 15980 KB Output is correct
13 Correct 81 ms 16108 KB Output is correct
14 Correct 93 ms 15980 KB Output is correct
15 Correct 88 ms 15980 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 16108 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 128 ms 16088 KB Output is correct
8 Correct 189 ms 16108 KB Output is correct
9 Correct 116 ms 16108 KB Output is correct
10 Correct 93 ms 16108 KB Output is correct
11 Correct 294 ms 16108 KB Output is correct
12 Correct 208 ms 16108 KB Output is correct
13 Correct 112 ms 16108 KB Output is correct
14 Correct 112 ms 16108 KB Output is correct
15 Correct 120 ms 16108 KB Output is correct