Submission #848362

#	Time	Username	Problem	Language	Result	Execution time	Memory
848362		vjudge1	Holding (COCI20_holding)	C++17	110 / 110	236 ms	17032 KiB

holding

#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;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 22 / 22