oj.uz

Submission #835332

# Submission time Handle Problem Language Result Execution time Memory
835332 2023-08-23T13:11:34 Z epicci23 Watching (JOI13_watching) C++17
100 / 100
 334 ms 31676 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())

inline int in()
{
  int x;cin >> x;
  return x;
}


void solve()
{
  int n=in(),p=in(),q=in();
  
  int ar[n+1];
  for(int i=1;i<=n;i++) ar[i]=in();

  sort(ar+1,ar+n+1);

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

  int dp[n+1][n+1];

  int l=1,r=(int)1e10;

  while(l<r)
  {
    int m=(l+r)/2;
    bool ok=0;
    for(int i=0;i<=n;i++)
     for(int j=0;j<=n;j++)
      dp[i][j]=3000;

    dp[0][0]=0;

    for(int i=1;i<=n;i++)
    {
      // use p
      int jl=1,jr=i;
      while(jl<jr)
      {
        int jm=(jl+jr)/2;
        if(ar[i]-ar[jm]+1<=m) jr=jm;
        else jl=jm+1;
      }
      
      for(int j=0;j<n;j++)
      {
        if(dp[jl-1][j]!=3000) 
          dp[i][j+1]=min(dp[i][j+1],dp[jl-1][j]);
      }

      // use q
      jl=1,jr=i;
      while(jl<jr)
      {
        int jm=(jl+jr)/2;
        if(ar[i]-ar[jm]+1<=2*m) jr=jm;
        else jl=jm+1;
      }

      for(int j=0;j<=n;j++)
      {
        if(dp[jl-1][j]!=3000) 
          dp[i][j]=min(dp[i][j],dp[jl-1][j]+1);
      }
    }

    for(int j=0;j<=p;j++) if(dp[n][j]<=q) {ok=1;break;}
    
    if(ok) r=m;
    else l=m+1;
  }
  
  cout << l << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//t=in();
  while(t--) solve();

  return 0;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 31572 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 299 ms 31672 KB Output is correct
8 Correct 322 ms 31672 KB Output is correct
9 Correct 311 ms 31676 KB Output is correct
10 Correct 328 ms 31572 KB Output is correct
11 Correct 327 ms 31672 KB Output is correct
12 Correct 334 ms 31676 KB Output is correct
13 Correct 307 ms 31572 KB Output is correct
14 Correct 330 ms 31668 KB Output is correct
15 Correct 324 ms 31672 KB Output is correct