Submission #844277

#	Time	Username	Problem	Language	Result	Execution time	Memory
844277		vjudge1	Holding (COCI20_holding)	C++17	88 / 110	43 ms	50780 KiB

holding

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 105
#define int long long

const int modulo = 1e9 + 7;

int arr[N], dp[N][N][1005];


int32_t main()
{
	fastio();


	int n, l, r, k;
	cin>>n>>l>>r>>k;

	for (int i = 1; i <= n; i++){
		cin>>arr[i];
	}

	int ans = 0;
	for (int i = l; i <= r; i++){
		ans += arr[i];
	}
	for (int i = r; i >= l; i--){
		for (int j = n; j >= 1; j--){
			if (j >= l && j <= r) continue;
			for (int m = 0; m <= k; m++){
				int nxt = j + 1;
				if (nxt == l) nxt = r + 1; 
				int t1 = dp[i][nxt][m];
				int t2 = dp[i + 1][j][m];
				int t3 = 0;
				if (m >= abs(i - j)) t3 = arr[j] - arr[i] + dp[i + 1][nxt][m - abs(i - j)];
				dp[i][j][m] = min(t3, min(t1, t2));
			}
		}
	}

	cout<<dp[l][1][k] + ans<<endl;
	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

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