Submission #1032378

#TimeUsernameProblemLanguageResultExecution timeMemory
10323780pt1mus23Holding (COCI20_holding)C++14
55 / 110
28 ms49312 KiB
#pragma GCC optimize("O3", "inline") #define skillissue <bits/stdc++.h> #define ultra_mal std #include skillissue using namespace ultra_mal; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define ins insert #define pb push_back #define int long long int #define pii pair<int, int> #define endl '\n' #define drop(x) cout<<(x)<<endl; return; #define all(x) x.begin(),x.end() #define hash FhashF const int mod = 1e9 +7, sze = 1e4 +10, inf = LLONG_MAX, P = 1453; // const int L = 30; int dp[111][111][sze]; int dp2[111][111][sze]; void optimus(){ int n,l,r,k; cin>>n>>l>>r>>k; vector<int> arr(n+1); for(int i=1;i<=n;i++){ cin>>arr[i]; } int sum=0; for(int i = l;i<=r;i++){ sum+=arr[i]; } for(int i =1;i<l;i++){ for(int j= l;j<=r;j++){ for(int p=0;p<=k;p++){ dp[i][j][p]= max({ dp[i-1][j][p], dp[i][j-1][p], (int)0 }); if((j-i)<=p){ dp[i][j][p]=max(dp[i][j][p],dp[i-1][j-1][p - (j-i)] + arr[j]-arr[i]); } // cout<<i<<" "<<j<<" "<<p<<" "<<dp[i][j][p]<<" "<< // dp[i-1][j-1][p - (j-i)]+ arr[i]- arr[j]<<endl; } } } /* r+1- >n l->r */ for(int i =l;i<=r;i++){ for(int j= r+1;j<=n;j++){ for(int p=0;p<=k;p++){ dp2[i][j][p]= max({ dp2[i+1][j][p], dp2[i][j+1][p], (int)0 }); if((j-i)<=p){ dp2[i][j][p]=max(dp2[i][j][p],dp2[i+1][j-1][p - (j-i)] + arr[j]-arr[i]); } // cout<<i<<" "<<j<<" "<<p<<" "<<dp[i][j][p]<<" "<< // dp[i-1][j-1][p - (j-i)]+ arr[i]- arr[j]<<endl; } } } int mx =0 ; for(int i = l-1;i<=r;i++){ for(int j=0;j<=k;j++){ mx=max(mx, dp[l-1][i][j] + dp[n][i+1][k - j]); } } drop(sum - mx); } signed main() { cin.tie(0)->sync_with_stdio(0); int tt = 1; // cin>>tt; while(tt--){ optimus(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...