// NgJaBach: Forever Meadow <3
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long int ll;
typedef unsigned long long ull;
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define bend(a) a.begin(),a.end()
#define rev(x) reverse(bend(x))
#define mset(a) memset(a, 0, sizeof(a))
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define endl '\n'
const int N=105,M=1000000007;
const ll INF=1e18+7;
int n,L,R,k,a[N];
namespace sub2{
int dp[N][N][N*N/4];
int solve(){
k=min(k,n*n/4);
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j){
for(int d=0;d<=k;++d){
dp[i][j][d]=0;
}
}
}
for(int i=1;i<L;++i){
for(int j=L;j<=n;++j){
for(int d=0;d<=k;++d){
dp[i][j][d]=max(dp[i-1][j][d],dp[i][j-1][d]);
int cost=j-i;
if(d>=cost) dp[i][j][d]=max(dp[i][j][d],dp[i-1][j-1][d-cost]+a[j]-a[i]);
}
}
}
int ans,sum=0;
ans=dp[L-1][n][k];
for(int i=L;i<=R;++i) sum+=a[i];
return sum-ans;
}
}
namespace sub4{
int dpL[N][N][N*N/4],dpR[N][N][N*N/4];
int solve(){
k=min(k,n*n/4);
for(int i=0;i<=n+1;++i){
for(int j=0;j<=n+1;++j){
for(int d=0;d<=k;++d){
dpL[i][j][d]=0;
dpR[i][j][d]=0;
}
}
}
for(int i=1;i<L;++i){
for(int j=L;j<=R;++j){
for(int d=0;d<=k;++d){
dpL[i][j][d]=max(dpL[i-1][j][d],dpL[i][j-1][d]);
int cost=j-i;
if(d>=cost) dpL[i][j][d]=max(dpL[i][j][d],dpL[i-1][j-1][d-cost]+a[j]-a[i]);
}
}
}
for(int i=n;i>R;--i){
for(int j=R;j>=L;--j){
for(int d=0;d<=k;++d){
dpR[i][j][d]=max(dpR[i+1][j][d],dpR[i][j+1][d]);
int cost=i-j;
if(d>=cost) dpR[i][j][d]=max(dpR[i][j][d],dpR[i+1][j+1][d-cost]+a[j]-a[i]);
}
}
}
int ans=0,sum=0;
for(int i=L-1;i<=R;++i){
for(int d=0;d<=k;++d){
ans=max(ans,dpL[L-1][i][d]+dpR[R+1][i+1][k-d]);
}
}
for(int i=L;i<=R;++i) sum+=a[i];
// cout<<sum<<" "<<ans<<endl;
return sum-ans;
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
// freopen("DEBT.inp","r",stdin);
// freopen("DEBT.out","w",stdout);
cin>>n>>L>>R>>k;
for(int i=1;i<=n;++i) cin>>a[i];
// if(n<=50 and R==n) cout<<sub2::solve();
// else
cout<<sub4::solve();
return 0;
}
/*
==================================+
INPUT: |
------------------------------ |
------------------------------ |
==================================+
OUTPUT: |
------------------------------ |
------------------------------ |
==================================+
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
6 ms |
35164 KB |
Output is correct |
3 |
Correct |
4 ms |
35364 KB |
Output is correct |
4 |
Correct |
4 ms |
35164 KB |
Output is correct |
5 |
Correct |
4 ms |
35164 KB |
Output is correct |
6 |
Correct |
4 ms |
35164 KB |
Output is correct |
7 |
Correct |
4 ms |
35160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
6 ms |
35164 KB |
Output is correct |
3 |
Correct |
4 ms |
35364 KB |
Output is correct |
4 |
Correct |
4 ms |
35164 KB |
Output is correct |
5 |
Correct |
4 ms |
35164 KB |
Output is correct |
6 |
Correct |
4 ms |
35164 KB |
Output is correct |
7 |
Correct |
4 ms |
35160 KB |
Output is correct |
8 |
Correct |
28 ms |
97876 KB |
Output is correct |
9 |
Correct |
13 ms |
99676 KB |
Output is correct |
10 |
Correct |
12 ms |
98116 KB |
Output is correct |
11 |
Correct |
12 ms |
101720 KB |
Output is correct |
12 |
Correct |
11 ms |
98140 KB |
Output is correct |
13 |
Correct |
14 ms |
103516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
6 ms |
35164 KB |
Output is correct |
3 |
Correct |
4 ms |
35364 KB |
Output is correct |
4 |
Correct |
4 ms |
35164 KB |
Output is correct |
5 |
Correct |
4 ms |
35164 KB |
Output is correct |
6 |
Correct |
4 ms |
35164 KB |
Output is correct |
7 |
Correct |
4 ms |
35160 KB |
Output is correct |
8 |
Correct |
28 ms |
97876 KB |
Output is correct |
9 |
Correct |
13 ms |
99676 KB |
Output is correct |
10 |
Correct |
12 ms |
98116 KB |
Output is correct |
11 |
Correct |
12 ms |
101720 KB |
Output is correct |
12 |
Correct |
11 ms |
98140 KB |
Output is correct |
13 |
Correct |
14 ms |
103516 KB |
Output is correct |
14 |
Correct |
11 ms |
100956 KB |
Output is correct |
15 |
Correct |
12 ms |
99672 KB |
Output is correct |
16 |
Correct |
12 ms |
99676 KB |
Output is correct |
17 |
Correct |
12 ms |
100184 KB |
Output is correct |
18 |
Correct |
12 ms |
100444 KB |
Output is correct |
19 |
Correct |
14 ms |
102144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
18776 KB |
Output is correct |
2 |
Correct |
6 ms |
35164 KB |
Output is correct |
3 |
Correct |
4 ms |
35364 KB |
Output is correct |
4 |
Correct |
4 ms |
35164 KB |
Output is correct |
5 |
Correct |
4 ms |
35164 KB |
Output is correct |
6 |
Correct |
4 ms |
35164 KB |
Output is correct |
7 |
Correct |
4 ms |
35160 KB |
Output is correct |
8 |
Correct |
28 ms |
97876 KB |
Output is correct |
9 |
Correct |
13 ms |
99676 KB |
Output is correct |
10 |
Correct |
12 ms |
98116 KB |
Output is correct |
11 |
Correct |
12 ms |
101720 KB |
Output is correct |
12 |
Correct |
11 ms |
98140 KB |
Output is correct |
13 |
Correct |
14 ms |
103516 KB |
Output is correct |
14 |
Correct |
11 ms |
100956 KB |
Output is correct |
15 |
Correct |
12 ms |
99672 KB |
Output is correct |
16 |
Correct |
12 ms |
99676 KB |
Output is correct |
17 |
Correct |
12 ms |
100184 KB |
Output is correct |
18 |
Correct |
12 ms |
100444 KB |
Output is correct |
19 |
Correct |
14 ms |
102144 KB |
Output is correct |
20 |
Correct |
35 ms |
163240 KB |
Output is correct |
21 |
Correct |
38 ms |
178120 KB |
Output is correct |
22 |
Correct |
28 ms |
147792 KB |
Output is correct |
23 |
Correct |
67 ms |
229716 KB |
Output is correct |
24 |
Correct |
41 ms |
165200 KB |
Output is correct |
25 |
Correct |
76 ms |
229712 KB |
Output is correct |