제출 #844654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844654		serifefedartar	Holding (COCI20_holding)	C++17	110 / 110	209 ms	8936 KiB

holding

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 1e6 + 5;

vector<int> A;
vector<vector<int>> dp;
int main() {
	fast
	int N, L, R, K;
	cin >> N >> L >> R >> K;

	A = vector<int>(N+1);
	dp = vector<vector<int>>(102, vector<int>(10205, 1e9));
	for (int i = 1; i <= N; i++)
		cin >> A[i];

	dp[0][0] = 0;
	int ans = 1e9;
	for (int i = 1; i <= N; i++) {
		vector<vector<int>> new_dp(102, vector<int>(10205, 1e9));
		for (int cnt = 0; cnt <= i; cnt++) {
			int cost = abs(L + cnt - i);
			for (int last = 0; last <= K; last++) {
				new_dp[cnt][last] = min(new_dp[cnt][last], dp[cnt][last]); 
				new_dp[cnt + 1][cost + last] = min(new_dp[cnt + 1][cost + last], dp[cnt][last] + A[i]);
				if (cnt+1 == R - L + 1 && cost + last <= K)
					ans = min(ans, new_dp[cnt+1][cost+last]);
			}
		}
		dp = new_dp;
	}
	cout << ans << "\n"; 
}

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