Submission #249657

#	Time	Username	Problem	Language	Result	Execution time	Memory
249657		dvdg6566	Holding (COCI20_holding)	C++14	55 / 110	75 ms	16512 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=100;
const ll MAXK=10100;
const ll INF = 1e9;
const ll MOD = 1e9+7;

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

int ask(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,ask(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 main(){
	memset(dpleft,-1,sizeof(dpleft));
	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;
	}
	assert(R==N);
	for(int i=0;i<L;++i)dpleft[i][0][0]=0;
	for(int r=L;r<=R;++r){
		for(int l=0;l<L;++l)for(int k=0;k<=K;++k)ask(l,r,k);
		// cout<<"When right pointer at "<<r<<'\n';
		// for(int l=0;l<L;++l){
		// 	cout<<"Left at "<<l<<'\n';
		// 	for(int k=0;k<=K;++k)cout<<ask(l,r,k)<<' ';cout<<'\n';
		// }
		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;
		}
	}
	int res=INF;
	for(int k=0;k<=K;++k){
		res=min(res,dpleft[L-1][k][0]);
	}
	cout<<res;
}

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