Submission #1071465

#TimeUsernameProblemLanguageResultExecution timeMemory
1071465FIFI_cppWatching (JOI13_watching)C++17
100 / 100
155 ms16132 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll, ll> #define pii pair<int, int> #define fs first #define sc second #define pb push_back void solve() { int n,p,q; cin>>n>>p>>q; int a[n+1]; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); p=min(p,n); q=min(q,n); int l=1,r=1e9; while(l<r){ int m=(l+r)/2; int dp[n+1][q+1]; for(int i=0;i<=q;i++)dp[0][i]=0; int idx1=1,idx2=1; for(int i=1;i<=n;i++){ while(a[i]-a[idx1]+1>m)idx1++; while(a[i]-a[idx2]+1>2*m)idx2++; for(int j=0;j<=q;j++){ dp[i][j]=dp[idx1-1][j]+1; if(j){ dp[i][j]=min(dp[i][j],dp[idx2-1][j-1]); } } } if(dp[n][q]<=p)r=m; else l=m+1; } cout<<l; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...