Submission #1032220

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
10322202024-07-23 13:27:01HasanV11010238Holding (COCI20_holding)C++17
88 / 110
113 ms262144 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 10000000000000
int main(){
int n, l, r, am;
cin>>n>>l>>r>>am;
vector<ll> v(n + 1, 0);
for (int i = 1; i <= n; i++){
cin>>v[i];
}
int m = (r - l + 1);
vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(m + 1, vector<ll>(am + 1, INF)));
dp[0][0][0] = 0;
ll ans = INF;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= min(i, m); j++){
for (int k = 0; k <= am; k++){
dp[i][0][k] = 0;
dp[i][j][k] = dp[i - 1][j][k];
if (k - abs(i - (l + j - 1)) >= 0){
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][k - abs(i - (l + j - 1))] + v[i]);
}
if (j == m){
ans = min(ans, dp[i][j][k]);
}
}
}
}
cout<<ans;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...