제출 #291101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
291101		penguinhacker	Holding (COCI20_holding)	C++17	110 / 110	161 ms	2936 KiB

holding

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

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