Submission #249682

#	Time	Username	Problem	Language	Result	Execution time	Memory
249682		dvdg6566	Holding (COCI20_holding)	C++14	110 / 110	263 ms	8440 KiB

holding

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=105;
const ll MAXK=10100;
const ll INF = 1e9;
const ll MOD = 1e9+7;

int dpleft[MAXN][MAXK][2];
int dpright[MAXN][MAXK][2];
int rightends[MAXN][MAXK];
int leftends[MAXN][MAXK];
int N,L,R,K;
int A[MAXN];

int askLeft(int l,int r,int k){
	if(l<0||k<0)return INF;
	if(dpleft[l][k][1]!=-1)return dpleft[l][k][1];
	int ans=INF;
	ans=min(ans,askLeft(l-1,r,k));
	// choose to swap
	int len=(r-l);
	if(k>=len&&l>0)ans=min(ans,dpleft[l-1][k-len][0]+A[l]);
	// chose to not swap
	ans=min(ans,A[r]+dpleft[l][k][0]);
	return dpleft[l][k][1]=ans;
}

int askRight(int l,int r,int k){
	if(r>N+1||k<0)return INF;
	if(dpright[r][k][1]!=-1)return dpright[r][k][1];
	int ans=INF;
	ans=min(ans,askRight(l,r+1,k));
	// choose to swap
	int len=(r-l);
	if(k>=len&&r<N+1)ans=min(ans,dpright[r+1][k-len][0]+A[r]);
	// chose to not swap
	ans=min(ans,A[l]+dpright[r][k][0]);
	return dpright[r][k][1]=ans;
}

int main(){
	cin>>N>>L>>R>>K;
	for(int i=1;i<=N;++i)cin>>A[i];
	for(int l=0;l<L;++l)for(int k=0;k<=K;++k){
		dpleft[l][k][0]=INF;
		dpleft[l][k][1]=-1;
	}
	for(int i=0;i<L;++i)dpleft[i][0][0]=0;
	for(int r=L;r<=R;++r){
		for(int k=0;k<=K;++k){
			rightends[r][k]=askLeft(L-1,r,k);
		}

		for(int l=0;l<L;++l)for(int k=0;k<=K;++k){
			dpleft[l][k][0]=dpleft[l][k][1];
			dpleft[l][k][1]=-1;
		}
	}

	for(int r=R+1;r<=N+1;++r)for(int k=0;k<=K;++k){
		dpright[r][k][0]=INF;
		dpright[r][k][1]=-1;
	}
	for(int i=R+1;i<=N+1;++i)dpright[i][0][0]=0;
	for(int l=R;l>=L;--l){
		for(int k=0;k<=K;++k){
			leftends[l][k]=askRight(l,R+1,k);
		}
		for(int r=R+1;r<=N+1;++r)for(int k=0;k<=K;++k){
			dpright[r][k][0]=dpright[r][k][1];
			dpright[r][k][1]=-1;
		}
	}

	for(int div=L;div<=R;++div){
		for(int k=1;k<=K;++k)rightends[div][k]=min(rightends[div][k],rightends[div][k-1]);
		for(int k=1;k<=K;++k)leftends[div][k]=min(leftends[div][k],leftends[div][k-1]);
		// cout<<"Stop left side at "<<div<<'\n';
		// for(int k=0;k<=K;++k)cout<<rightends[div][k]<<' ';cout<<'\n';
	}

	// for(int div=L;div<=R;++div){
	// 	cout<<"Stop right side at "<<div<<'\n';
	// 	for(int k=0;k<=K;++k)cout<<leftends[div][k]<<' ';cout<<'\n';
	// }

	int res=INF;
	for(int div=L-1;div<=R;++div){
		for(int k=0;k<=K;++k){
			res=min(res, rightends[div][k] + leftends[div+1][K-k]);
		}
	}
	cout<<res;
}

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