제출 #1264983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264983		goulthen	Holding (COCI20_holding)	C++20	88 / 110	253 ms	327680 KiB

holding

#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define fi first
#define se second

const int MAXN = 1e2 + 10;
const int INF = 1e9+10;
int a[MAXN], dp[MAXN][MAXN][10001], dp2[MAXN][MAXN][10001];

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,l,r,K, s=0;cin >> n >> l >> r >> K;
	rep(i,1,n) cin >> a[i];
	rep(i,l,r) s+=a[i];

	rep(j,0,n) rep(k,0,K) dp[0][j][k] = dp2[n+1][j][k]= INF;
	dp[0][0][0] = dp2[n+1][0][0] = 0;

	rep(i,1,l-1) {
		rep(j,0,n) {
			rep(k,0,K) {
				dp[i][j][k] = dp[i-1][j][k];
				if (j > 0 && k >= l-i) dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k-(l-i)] + a[i]);
			}
		}
	}

	rep(i,l,n) {
		rep(j,0,n) {
			rep(k,0,K) {
				dp[i][j][k] = dp[i-1][j][k];
				if (k >= i-l) dp[i][j][k] = min(dp[i][j][k], dp[i-1][j+1][k-(i-l)] - a[i]);
			}
		}
	}


	per(i,n,r+1) {
		rep(j,0,n) {
			rep(k,0,K) {
				dp2[i][j][k] = dp2[i+1][j][k];
				if (j > 0 && k >= i-r) dp2[i][j][k] = min(dp2[i][j][k], dp2[i+1][j-1][k-(i-r)] + a[i]);
			}
		}
	}

	per(i,r,1) {
		rep(j,0,n) {
			rep(k,0,K) {
				dp2[i][j][k] = dp2[i+1][j][k];
				if (k >= r-i) dp2[i][j][k] = min(dp2[i][j][k], dp2[i+1][j+1][k-(r-i)] - a[i]);
			}
		}
	}

	rep(i,1,n) rep(j,0,n) rep(k,1,K) dp[i][j][k] = min(dp[i][j][k], dp[i][j][k-1]);
	rep(i,1,n) rep(j,0,n) rep(k,1,K) dp2[i][j][k] = min(dp2[i][j][k], dp2[i][j][k-1]);

	int x = 0;

	rep(mid,l-1,r) {
		rep(k,0,K) {
			x = min(x, dp[mid][0][k] + dp2[mid+1][0][K-k]);
		}
	}
	cout << s + x << '\n';
	return 0;
}

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