Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define all(a) a.begin(),a.end()
- #define F first
- #define S second
- #define pb push_back
- #define ll long long
- #define vi vector<int>
- #define pi pair<int,int>
- #define mp make_pair
- #ifdef LOCAL
- #include "debug.h"
- #else
- #define debug(...) 42
- #endif
- const int mod=1e9+7;
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- int mul(int a,int b)
- {
- return ((a)*1ll*(b))%mod;
- }
- void add(int &a,int b)
- {
- a+=b;
- if(a>=mod)a-=mod;
- }
- int sub(int a,int b){
- a-=b;
- if(a<0){
- a+=mod;
- }
- return a;
- }
- int powz(int a,int b)
- {
- int res=1;
- while(b)
- {
- if(b&1){
- res=mul(res,a);
- }
- b/=2;
- a=mul(a,a);
- }
- return res;
- }
- template <typename A, typename B>
- istream& operator>>(istream& input,pair<A,B>& x) {
- input>>x.F>>x.S;
- return input;
- }
- template <typename A>
- istream& operator>>(istream& input,vector<A>& x) {
- for(auto& i:x)
- input>>i;
- return input;
- }
- template<typename A>
- ostream& operator<<(ostream& output,vector<A>& x) {
- for(auto& i:x)
- output<<i<<' ';
- return output;
- }
- const int N=1000002;
- int dp[105][10005],dp2[105][10005],new_dp[105][10005];
- void solve(){
- int n,l,r,k;
- cin>>n>>l>>r>>k;
- vi a(n);
- cin>>a;
- int tot=r-l+1;
- l--;r--;
- for(int i=0;i<l;i++){
- for(int j=0;j<=tot-1;j++){
- for(int put=j+1;put<=tot;put++){
- int tott=abs(put+l-1-i),val=a[l+put-1]-a[i];
- if(val<=0){
- continue;
- }
- for(int cost=0;cost<=k-tott;cost++){
- new_dp[put][cost+tott]=max(new_dp[put][cost+tott],dp[j][cost]+val);
- }
- }
- }
- for(int j=0;j<=tot;j++){
- for(int cost=0;cost<=k;cost++){
- dp[j][cost]=max(dp[j][cost],new_dp[j][cost]);
- new_dp[j][cost]=0;
- }
- }
- }
- for(int i=n-1;i>r;i--){
- for(int j=0;j<=tot-1;j++){
- for(int put=j+1;put<=tot;put++){
- int tott=abs(r-put+1-i),val=a[r-put+1]-a[i];
- if(val<=0){
- continue;
- }
- for(int cost=0;cost<=k-tott;cost++){
- new_dp[put][cost+tott]=max(new_dp[put][cost+tott],dp2[j][cost]+val);
- }
- }
- }
- for(int j=0;j<=tot;j++){
- for(int cost=0;cost<=k;cost++){
- dp2[j][cost]=max(dp2[j][cost],new_dp[j][cost]);
- new_dp[j][cost]=0;
- }
- }
- }
- vector<vector<int>>calc(n+1,vector<int>(10005));
- for(int j=0;j<=tot;j++){
- for(int cost=0;cost<=k;cost++){
- if(cost){
- calc[j][cost]=max({calc[j][cost],calc[j][cost-1],dp[j][cost]});
- }
- else{
- calc[j][cost]=dp[j][cost];
- }
- }
- }
- int ans=0;
- for(int i=0;i<=tot;i++){
- for(int j=0;j<=tot-i;j++){
- for(int cost=0;cost<=k;cost++){
- int cost2=k-cost;
- ans=max(ans,calc[i][cost2]+dp2[j][cost]);
- }
- }
- }
- int sum=ans;
- sum*=-1;
- for(int i=l;i<=r;i++){
- sum+=a[i];
- }
- cout<<sum;
- }
- signed main(){
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int tc=1;
- //~cin>>tc;
- for(int _=0;_<tc;_++){
- //~ cout<<"Case #"<<_+1<<": ";
- solve();
- if(_!=tc-1)
- cout<<"\n";
- }
- }
Add Comment
Please, Sign In to add comment