Submission #73790

#TimeUsernameProblemLanguageResultExecution timeMemory
73790KLPPSemiexpress (JOI17_semiexpress)C++14
48 / 100
1073 ms23296 KiB
#include<iostream>
#include<stdio.h>

using namespace std;
typedef long long int lld;
lld calculatestations(lld N,lld T, lld A, lld B,int S){//N estacoes, tempo minimo T, A normal, B semiexpresso,S estacoes semiexpresso
	//cout<<N<<" "<<T<<" "<<A<<" "<<B<<" "<<S<<endl;
	if(T<0)return 0;
	//if(T==0)return 1;
	if(A*(N-1)<=T)return N;
	int pos=T/A;
	//cout<<pos<<endl;
	if(S==0)return pos+1;
	return 1+pos+calculatestations(N-pos-1,T-B*(pos+1),A,B,S-1);
}
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	k-=m;
	lld a,b,c;
	cin>>a>>b>>c;
	lld arr[m];
	lld cost[m][k+1];
	lld T;
	cin>>T;
	for(int i=0;i<m;i++)cin>>arr[i];
	for(int i=0;i<m-1;i++){
		for(int j=0;j<=k;j++){
			cost[i][j]=calculatestations(arr[i+1]-arr[i],T-b*arr[i]+b,a,c,j);
			//cout<<i<<" "<<j<<" "<<cost[i][j]<<" "<<arr[i+1]-arr[i]<<endl;
		}
	}
	lld ans=0;
	if(b*(n-1)>T)ans--;
	lld DP[m][k+1];
	
	for(int i=0;i<m;i++){
		for(int j=0;j<=k;j++)DP[i][j]=-1000000;
	}
	for(int i=0;i<=k;i++)DP[0][i]=0;
	for(int i=1;i<m;i++){
		for(int j=0;j<=k;j++){
			for(int l=0;j+l<=k;l++){
				DP[i][j+l]=max(DP[i][j+l],cost[i-1][l]+DP[i-1][j]);
			}
		}
	}
	/*for(int i=0;i<m;i++){
		for(int j=0;j<=k;j++)cout<<DP[i][j]<<" ";
		cout<<endl;
	}*/
	ans+=DP[m-1][k];
	cout<<ans<<endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...