Submission #1207548

#TimeUsernameProblemLanguageResultExecution timeMemory
1207548ricardsjansonsWatching (JOI13_watching)C++20
100 / 100
347 ms472 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") using namespace std; const int N=2005; int n,p,q; int a[N]; vector<vector<int>>dp(2,vector<int>(N)); bool f(int w){ for(int i=0;i<=p;i++){ if(i){ dp[0]=dp[1]; }else{ dp[0].assign(q+2,0); } for(int j=0;j<=q;j++){ int pos=dp[0][j]; pos=min(pos,n-1); dp[1][j]=upper_bound(a+pos+1,a+n+1,a[pos+1]+w-1)-a-1; int&x=dp[0][j+1]; x=max(x,(int)(upper_bound(a+pos+1,a+n+1,a[pos+1]+2*w-1)-a-1)); } } //cout<<dp[0][q]<<endl; return dp[0][q]>=n; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>p>>q; for(int i=1;i<=n;i++){ cin>>a[i]; } if(n<=p+q){ cout<<1; return 0; } sort(a+1,a+n+1); //cout<<f(4)<<endl; int l=1,r=1e9; while(l<r){ int mid=(l+r)/2; if(f(mid)){ r=mid; }else{ l=mid+1; } } cout<<l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...