#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int INF=1e9;
int n, l, r, k, a[100];
//int dp[10000][100]; //minimum cost given used i operations and have selected from first j elements
//what do we need to know
//we need cost used, used first [] elements, and have chosen first [] elements
//maybe only maintain 2 things, such as cost, and chosen first [] elements
void debug(vector<vector<int>> &v) {
for (auto& x: v) {
for (int i: x) cout << i << " ";
cout << "\n";
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> l >> r >> k, --l, --r;
for (int i=0; i<n; ++i) cin >> a[i];
//memset(dp, 0x3f, sizeof(dp));
vector<vector<int>> dp(k+1, vector<int>(r-l+2, INF));
dp[0][0]=0;
for (int pos=0; pos<n; ++pos) {
//vector<vector<int>> dpl=dp;
for (int i=min(r-l+1, pos+1); i>0; --i) {
int cost=abs(l+i-1-pos);
for (int j=k; j>=cost; --j) dp[j][i]=min(dp[j][i], dp[j-cost][i-1]+a[pos]);
//for (int j=cost; j<=k; ++j) dp[j][i]=min(dp[j][i], dpl[j-cost][i-1]+a[pos]);
}
//debug(dp);
}
int ans=INF;
for (int i=0; i<=k; ++i) ans=min(ans, dp[i][r-l+1]);
cout << ans << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1024 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
40 ms |
1792 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
40 ms |
1792 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
40 ms |
1792 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
40 ms |
1792 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
40 ms |
1792 KB |
Output is correct |
| 20 |
Correct |
2 ms |
384 KB |
Output is correct |
| 21 |
Correct |
2 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
3 ms |
512 KB |
Output is correct |
| 24 |
Correct |
5 ms |
384 KB |
Output is correct |
| 25 |
Correct |
161 ms |
2936 KB |
Output is correct |
