Submission #73803

#	Time	Username	Problem	Language	Result	Execution time	Memory
73803		KLPP	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	60 ms	33676 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;
    	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]=0;
			if(j>0)cost[i][j]=cost[i][j-1];
    			cost[i][j]+=calculatestations(arr[i+1]-arr[i]-cost[i][j],T-b*arr[i]-c*cost[i][j]+b,a,c,0);
    			//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:11: 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:11: 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:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%lld",&T);
      ~~~~~^~~~~~~~~~~
semiexpress.cpp:43:31: 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]);
                          ~~~~~^~~~~~~~~~~~~~~~

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