This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long maxn=1000+10;
const long long logn=25;
long long n,k,t;
long long x[maxn];
long long dp[maxn][maxn];
long long kol=0;
long long f(long long L,long long R)
{
if(L==0 && R==n-1)
{
return true;
}
long long rez=0;
if(R<n-1 && (x[R+1]-x[L])<=(R-L+1)*t*(2*kol))
{
rez=max(rez,f(L,R+1));
}
if(L>0 && (x[R]-x[L-1])<=(R-L+1)*t*(2*kol))
{
rez=max(rez,f(L-1,R));
}
return rez;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>k>>t;
k--;
memset(dp,-1,sizeof dp);
for(long long i=0;i<n;i++)
{
cin>>x[i];
}
long long l=0;
long long r=x[n-1]-x[0];
long long ans=0;
while(l<=r)
{
long long mid=l+(r-l)/2;
kol=mid;
if(f(k,k))
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
cout<<ans<<endl;
/*long long m,n;
cin>>m>>n;
long long mi=2e9;
long long mx=-1;
vector<pair<pair<long long,long long>,pair<long long,long long>>>p;
vector<pair<pair<long long,long long>,pair<long long,long long>>>x;
for(long long i=0;i<m;i++)
{
long long a,b,c,d;
cin>>a>>b>>c>>d;
p.push_back({{a,b},{c,d}});
mi=min(mi,a);
mx=max(mx,b);
}
n=mx-mi+1;
map<long long,long long>m;
long long cnt=0;
for(long long i=mi;i<=mx;i++)
{
m[i]=cnt;
cnt++;
}
for(long long i=0;i<m;i++)
{
long long a=p.first.first;
long long b=p.first.second;
long long c=p.second.first;
long long d=p.second.second;
x.push_back({{m[a],m[b]},{m[c],m[d]}});
}*/
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |