/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define cerr if(false)cerr
const int N = 5000+100, M = 1e5+10, K = 52, MX = 30;
ll n, k, T, a[N];
array<ll, 3> dp[N][N][2];
void solve(){
cin >> n >> k >> T;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
int L = 0, R = 1e9, ans = 0;
while(L <= R){
ll S = L+R>>1;
for(int i = 1; i <= n; ++i){
for(int j = i; j <= n; ++j) dp[i][j][0] = dp[i][j][1] = {0, 0, 0};
}
cerr << S << '\n';
dp[k][k][0] = dp[k][k][1] = {1, a[k], a[k]};
for(int d = 1; d <= n; ++d){
for(int l = 1; l + d <= n; ++l){
int r = l + d;
vi V = {l, r};
array<ll, 3> v = {0, 0, 0};
array<ll, 3> q = {0, 0, 0};
for(int p = 0; p < 2; ++p){
if(dp[l + 1][r][p][0]){
if(v[0]){
v[1] = min(v[1], dp[l + 1][r][p][1] - S * T);
v[2] = max(v[2], dp[l + 1][r][p][2] + S * T);
}else{
v[0] = 1;
v[1] = dp[l + 1][r][p][1] - S * T;
v[2] = dp[l + 1][r][p][2] + S * T;
}
}
if(dp[l][r - 1][p][0]){
if(q[0]){
q[1] = min(q[1], dp[l][r - 1][p][1]);
q[2] = max(q[2], dp[l][r - 1][p][2]);
}else{
q[0] = 1;
q[1] = dp[l][r - 1][p][1] - S * T;
q[2] = dp[l][r - 1][p][2] + S * T;
}
}
}
if(v[0] && v[1] <= a[l] + (r-l)*S*T)
dp[l][r][0] = {v[0], v[1], min(v[2], a[l] + (r-l)*S*T)};
if(q[0] && q[2] >= a[r] - (r-l)*S*T)
dp[l][r][1] = {q[0], max(q[1], a[r] - (r-l)*S*T), q[2]};
cerr << l << ' ' << r << " :\n";
cerr << dp[l][r][0][0] << ' ' << dp[l][r][0][1] << ' ' << dp[l][r][0][2] << '\n';
cerr << v[0] << ' ' << v[1] << ' ' << v[2] << '\n';
cerr << dp[l][r][1][0] << ' ' << dp[l][r][1][1] << ' ' << dp[l][r][1][2] << '\n';
cerr << q[0] << ' ' << q[1] << ' ' <<q[2] << '\n';
cerr << '\n';
}
cerr <<'\n';
}
if(dp[1][n][0][0] || dp[1][n][1][0]){
R = S - 1;
ans = S;
}else L = S + 1;
}
cout << ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
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... |