This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 105
using namespace std;
int arr[N];
int32_t main(){
fast
int n, l, r, money;
cin>>n>>l>>r>>money;
int sum = 0;
for(int i = 1; i <= n; i++) {
cin>>arr[i];
if(i >= l and i <= r) sum += arr[i];
}
vector <vector<int> > dp(n + 2, vector<int> (money + 1, inf));
dp[l][0] = sum;
for(int i = 1; i <= n; i++) { // from
if(i >= l and i <= r) continue; //!
vector <vector<int> > ndp = dp;
for(int j = l; j <= r; j++) { // to
for(int k = 0; k <= money; k++) { // k
// swapped j and i
if(k + abs(i - j) <= money) {
// cout<<i<<" "<<j<<" | ";
ndp[j + 1][k + abs(i - j)] = min(
ndp[j + 1][k + abs(i - j)],
dp[j][k] + (arr[i] - arr[j])
);
// if(ndp[j + 1][k + abs(i - j)] < 100)
// cout<<j + 1<<" "<<k + abs(i - j)<<" "<<ndp[j + 1][k + abs(i - j)]<<"\n";
}
dp[j + 1][k] = min(
dp[j + 1][k],
dp[j][k]
);
}
}
dp = ndp;
// cout<<"changed\n\n";
}
// cout<<"dp: ";
for(auto &it:dp) {
for(auto &itt:it) {
sum = min(sum, itt);
// if(itt < 100) cout<<itt<<" ";
}
}
cout<<sum;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |