제출 #1264989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264989		goulthen	Holding (COCI20_holding)	C++20	55 / 110	65 ms	11332 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[2][MAXN][10001], dp2[2][MAXN][10001], ans[MAXN][10001], ans2[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)%2][j][k]= INF;
	dp[0][0][0] = dp2[(n+1)%2][0][0] = 0;

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

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

			}
		}
	}


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

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

	int x = 0;

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

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