Submission #917651

#	Time	Username	Problem	Language	Result	Execution time	Memory
917651		Aiperiii	Watching (JOI13_watching)	C++14	100 / 100	670 ms	32508 KiB

watching

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
   ios_base::sync_with_stdio();
   cin.tie(0);cout.tie(0);
   int n,p,q;
   cin>>n>>p>>q;
   p=min(n,p);
   q=min(n,q);
   vector <int> a(n);
   for(int i=0;i<n;i++)cin>>a[i];
   sort(all(a));
   int l=0,r=1e10;
   
  while(l+1<r){
      int md=(l+r)/2;
      bool ok=0;
      vector <vector <int> > dp(n+1,vector <int> (p+1,1e9));
      for(int i=0;i<=p;i++)dp[0][i]=0;
      for(int i=1;i<=n;i++){
         auto pos1=lower_bound(all(a),a[i-1]-md*2+1)-a.begin();
         auto pos2=lower_bound(all(a),a[i-1]-md+1)-a.begin();
         for(int j=0;j<=p;j++){
            dp[i][j]=min(dp[i][j],dp[pos1][j]+1);
            if(j>0)dp[i][j]=min(dp[i][j],dp[pos2][j-1]);
         }
      }
      if(dp[n][p]<=q)ok=1;
      if(ok)r=md;
      else l=md;
   }
   cout<<r<<"\n";
}
/*
 13 3 2 33
 66
 99
 10
 83
 68
 19
 83
 93
 53
 15
 66
 75
 */

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