Submission #73794

#	Time	Username	Problem	Language	Result	Execution time	Memory
73794		KLPP	Semiexpress (JOI17_semiexpress)	C++14	48 / 100	1076 ms	33772 KiB

semiexpress

#include<iostream>
#include<stdio.h>

using namespace std;
typedef long long int lld;
lld DP[4000][4000];
lld cost[4000][4000];
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);
}
void computeDP(int x, int y, int lo, int hi,int level){
	if(x>y)return;
	int bestindex=lo;
	int mid=(x+y)/2;
	for(int i=lo;i<=hi && i<=mid;i++){
		if(DP[level-1][mid-i]+cost[level-1][i]>DP[level][mid]){
			DP[level][mid]=DP[level-1][mid-i]+cost[level-1][i];
			bestindex=i;
		}
	}
	computeDP(x,mid-1,lo,bestindex,level);
	computeDP(mid+1,y,bestindex,hi,level);
}
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	k-=m;
	lld a,b,c;
	cin>>a>>b>>c;
	lld arr[m];
	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--;
	
	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++){
		computeDP(0,k,0,k,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;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 0 / 52