Submission #870885

#TimeUsernameProblemLanguageResultExecution timeMemory
870885ngjabachHolding (COCI20_holding)C++14
110 / 110
76 ms229716 KiB
// 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...