Submission #198496

#	Time	Username	Problem	Language	Result	Execution time	Memory
198496		alishahali1382	Holding (COCI20_holding)	C++14	110 / 110	337 ms	240388 KiB

holding

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define upd(x, y) x=min(x, y);

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 105, LOG=20;

int n, m, k, L, R, x, y, t, a, b, ans;
int A[MAXN];
int dp[MAXN][MAXN][MAXN*MAXN>>1];
int dpL[MAXN][MAXN*MAXN>>1];
int dpR[MAXN][MAXN*MAXN>>1];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>L>>R>>k;
	for (int i=1; i<=n; i++) cin>>A[i];
	
	k=min(k, n*(n-1)/2);
	
	for (int i=L; i<=R; i++) for (int j=0; j<=k; j++) dp[i][0][j]=inf;
	for (int i=L; i<=R; i++) for (int ii=0; ii<=i; ii++){
		for (int j=0; j<=k; j++){
			dp[i][ii][j]=inf;
			if (ii) upd(dp[i][ii][j], dp[i][ii-1][j]);
			if (j) upd(dp[i][ii][j], dp[i][ii][j-1]);
			if (i-ii<=j && ii) upd(dp[i][ii][j], dp[i-1][ii-1][j-(i-ii)] + A[ii]);
		}
	}
	for (int i=L; i<=R; i++) for (int j=0; j<=k; j++) dpL[i][j]=dp[i][i][j];
	
	memset(dp, 0, sizeof(dp));
	for (int i=L; i<=R; i++) for (int j=0; j<=k; j++) dp[i][n+1][j]=inf;
	for (int i=R; i>=L; i--) for (int ii=n; ii>=i; ii--){
		for (int j=0; j<=k; j++){
			dp[i][ii][j]=inf;
			if (ii<n) upd(dp[i][ii][j], dp[i][ii+1][j]);
			if (j) upd(dp[i][ii][j], dp[i][ii][j-1]);
			if (ii-i<=j && ii<=n) upd(dp[i][ii][j], dp[i+1][ii+1][j-(ii-i)] + A[ii]);
		}
	}
	for (int i=L; i<=R; i++) for (int j=0; j<=k; j++) dpR[i][j]=dp[i][i][j];
	
	for (int i=L; i<=R; i++) ans+=A[i]; // :))
	for (int i=L-1; i<=R; i++) for (int j=0; j<=k; j++) ans=min(ans, dpL[i][j] + dpR[i+1][k-j]);
	cout<<ans<<'\n';
	/*
	debug2(dpL[1][0], dpR[2][3])
	debug(dp[2][3][3])
	debug2(dp[3][4][3-1] , A[3])
	debug(dp[3][5][2])*/
	
	return 0;
}
/*
5 2 3 3
21 54 12 2 0

*/

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