oj.uz

Submission #328711

# Submission time Handle Problem Language Result Execution time Memory
328711 2020-11-17T18:09:04 Z a_player Watching (JOI13_watching) C++14
100 / 100
 238 ms 15980 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;
  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 1 ms 748 KB Output is correct
2 Correct 0 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 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 1 ms 748 KB Output is correct
14 Correct 1 ms 748 KB Output is correct
15 Correct 1 ms 748 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 8428 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 46 ms 8428 KB Output is correct
8 Correct 127 ms 14188 KB Output is correct
9 Correct 40 ms 9324 KB Output is correct
10 Correct 30 ms 9068 KB Output is correct
11 Correct 238 ms 15980 KB Output is correct
12 Correct 134 ms 15980 KB Output is correct
13 Correct 46 ms 8556 KB Output is correct
14 Correct 38 ms 8428 KB Output is correct
15 Correct 35 ms 8428 KB Output is correct