Submission #1305456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305456		mikasa	Watching (JOI13_watching)	C++20	100 / 100	519 ms	30388 KiB

watching

#include<bits/stdc++.h>
using namespace std;
using intt=int32_t;
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define int long long
#define all(x) x.begin(),x.end()
#define pb push_back 

const int N=10001;
const int mod=1e9;
const int inf=2e9;
int n,p,q;
int a[N];

bool check(int x){
  vector<vector<int>> dp(n+1,vector<int>(p+1,inf));
  vector<int> sm(n+1,0);
  vector<int> la(n+1,0);
  for (int i=0;i<n;++i) {
    sm[i]=upper_bound(a+1,a+n+1,a[i+1]+x-1)-a-1;
    la[i]=upper_bound(a+1,a+n+1,a[i+1]+2*x-1)-a-1;
  }
  dp[0][0]=0;
  for (int i=0;i<n;++i) {
    for (int j=0;j<=p;++j) {
      if(j<p)dp[sm[i]][j+1]=min(dp[sm[i]][j+1],dp[i][j]);
      dp[la[i]][j]=min(dp[la[i]][j],dp[i][j]+1);
    }
  }
  int fl=0;
  for (int j=0;j<=p;++j) if (dp[n][j]<=q) fl=1;
  return fl;
}

void levi() {
  cin>>n>>p>>q;
  a[0]=1;
  for (int i=1;i<=n;++i) cin>>a[i];
  sort(a+1,a+n+1);
  if (p+q>=n) {
    cout<<1<<'\n';
    return;
  }
  int lo=1,hi=1e9;
  int res=1e9;
  while(lo<=hi) {
    int mid=lo+(hi-lo)/2;
    if (check(mid)) {
      res=mid;
      hi=mid-1;
    }
    else lo=mid+1;
  }
  cout<<res<<'\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);int tt=1;//cin>>tt;
  while(tt--)levi();
}

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