Submission #73796

#TimeUsernameProblemLanguageResultExecution timeMemory
73796KLPPSemiexpress (JOI17_semiexpress)C++14
48 / 100
1066 ms33688 KiB
#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;
	scanf("%d %d %d",&n,&m,&k);
	k-=m;
	lld a,b,c;
	//cin>>a>>b>>c;
	scanf("%lld %lld %lld",&a,&b,&c);
	lld arr[m];
	lld T;
	scanf("%lld",&T);
	//cin>>T;
	for(int i=0;i<m;i++)scanf("%lld",&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;
	printf("%lld",ans);
	return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&a,&b,&c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&T);
  ~~~~~^~~~~~~~~~~
semiexpress.cpp:43:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<m;i++)scanf("%lld",&arr[i]);
                      ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...